Was ist der Unterschied zwischen Bitverschiebung und arithmetischen Operationen?

Question

int aNumber;

aNumber = aValue / 2;
aNumber = aValue >> 1;

aNumber = aValue * 2;
aNumber = aValue << 1;

aNumber = aValue / 4;
aNumber = aValue >> 2;

aNumber = aValue * 8;
aNumber = aValue << 3;

// etc.

Was ist der "beste" Weg, um Operationen durchzuführen? Wann ist es besser, Bit-Shifting zu verwenden?

Answer 1

Solange Sie innerhalb der 2er-Potenzen multiplizieren oder dividieren, ist es schneller, mit einer Verschiebung zu arbeiten, da es sich um eine einzige Operation handelt (die nur einen Prozesszyklus benötigt).
Man gewöhnt sich recht schnell daran, << 1 als *2 und >>2 als /4 zu lesen, so dass ich nicht damit einverstanden bin, dass die Lesbarkeit bei der Verwendung von Shifting verloren geht, aber das ist jedem selbst überlassen.

Wenn du mehr Details über das Wie und Warum wissen willst, hilft dir vielleicht wikipedia weiter oder wenn du dir die Mühe machen willst, den Zusammenbau zu lernen ;-)

Answer 2

Als Beispiel für die Unterschiede ist dies eine x86-Assembly, die mit gcc 4.4 mit -O3 erstellt wurde

int arithmetic0 ( int aValue )
{
    return aValue / 2;
}

00000000 <arithmetic0>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 45 08                mov    0x8(%ebp),%eax
   6:   5d                      pop    %ebp
   7:   89 c2                   mov    %eax,%edx
   9:   c1 ea 1f                shr    $0x1f,%edx
   c:   8d 04 02                lea    (%edx,%eax,1),%eax
   f:   d1 f8                   sar    %eax
  11:   c3                      ret    

int arithmetic1 ( int aValue )
{
    return aValue >> 1;
}

00000020 <arithmetic1>:
  20:   55                      push   %ebp
  21:   89 e5                   mov    %esp,%ebp
  23:   8b 45 08                mov    0x8(%ebp),%eax
  26:   5d                      pop    %ebp
  27:   d1 f8                   sar    %eax
  29:   c3                      ret    

int arithmetic2 ( int aValue )
{
    return aValue * 2;
}

00000030 <arithmetic2>:
  30:   55                      push   %ebp
  31:   89 e5                   mov    %esp,%ebp
  33:   8b 45 08                mov    0x8(%ebp),%eax
  36:   5d                      pop    %ebp
  37:   01 c0                   add    %eax,%eax
  39:   c3                      ret    

int arithmetic3 ( int aValue )
{
    return aValue << 1;
}

00000040 <arithmetic3>:
  40:   55                      push   %ebp
  41:   89 e5                   mov    %esp,%ebp
  43:   8b 45 08                mov    0x8(%ebp),%eax
  46:   5d                      pop    %ebp
  47:   01 c0                   add    %eax,%eax
  49:   c3                      ret    

int arithmetic4 ( int aValue )
{
    return aValue / 4;
}

00000050 <arithmetic4>:
  50:   55                      push   %ebp
  51:   89 e5                   mov    %esp,%ebp
  53:   8b 55 08                mov    0x8(%ebp),%edx
  56:   5d                      pop    %ebp
  57:   89 d0                   mov    %edx,%eax
  59:   c1 f8 1f                sar    $0x1f,%eax
  5c:   c1 e8 1e                shr    $0x1e,%eax
  5f:   01 d0                   add    %edx,%eax
  61:   c1 f8 02                sar    $0x2,%eax
  64:   c3                      ret    

int arithmetic5 ( int aValue )
{
    return aValue >> 2;
}

00000070 <arithmetic5>:
  70:   55                      push   %ebp
  71:   89 e5                   mov    %esp,%ebp
  73:   8b 45 08                mov    0x8(%ebp),%eax
  76:   5d                      pop    %ebp
  77:   c1 f8 02                sar    $0x2,%eax
  7a:   c3                      ret    

int arithmetic6 ( int aValue )
{
    return aValue * 8;
}

00000080 <arithmetic6>:
  80:   55                      push   %ebp
  81:   89 e5                   mov    %esp,%ebp
  83:   8b 45 08                mov    0x8(%ebp),%eax
  86:   5d                      pop    %ebp
  87:   c1 e0 03                shl    $0x3,%eax
  8a:   c3                      ret    

int arithmetic7 ( int aValue )
{
    return aValue << 4;
}

00000090 <arithmetic7>:
  90:   55                      push   %ebp
  91:   89 e5                   mov    %esp,%ebp
  93:   8b 45 08                mov    0x8(%ebp),%eax
  96:   5d                      pop    %ebp
  97:   c1 e0 04                shl    $0x4,%eax
  9a:   c3                      ret    

Die Divisionen sind unterschiedlich - bei einer Zweierkomplement-Darstellung ergibt die Verschiebung einer negativen ungeraden Zahl um eins einen anderen Wert als die Division durch zwei. Aber der Compiler optimiert die Division trotzdem auf eine Folge von Verschiebungen und Additionen.

Der augenfälligste Unterschied ist jedoch, dass dieses Paar nicht dasselbe tut - eine Verschiebung um vier ist gleichbedeutend mit einer Multiplikation mit sechzehn, nicht mit acht! Sie würden wahrscheinlich keinen Fehler bekommen, wenn Sie den Compiler die kleinen Optimierungen für Sie durchführen lassen.

aNumber = aValue * 8;
aNumber = aValue << 4;

Answer 3

Wenn Sie große Berechnungen in einer Umgebung mit engen Schleifen durchführen müssen, bei denen die Rechengeschwindigkeit eine Rolle spielt, verwenden Sie Bitoperationen. (gilt als schneller als arithmetische Operationen)

Answer 4

Wenn es sich um Zahlen der Potenz 2 (2^x) handelt, ist es besser, Shifts zu verwenden - es geht nur darum, die Bits zu "schieben". (1 Assembler-Operation anstelle von 2 beim Dividieren).

Gibt es eine Sprache, deren Compiler diese Optimierung vornimmt?

Answer 5

int i = -11;
std::cout << (i  / 2) << '\n';   // prints -5 (well defined by the standard)
std::cout << (i >> 1) << '\n';   // prints -6 (may differ on other platform)

Je nach gewünschtem Rundungsverhalten können Sie die eine oder die andere Variante bevorzugen.