Warum teilt sich die 0x55555556 durch 3 Hack-Arbeit?

Question

Es gibt einen (relativ) bekannten Hack zum Teilen einer 32-Bit-Nummer durch drei. Anstelle der tatsächlichen teuren Division kann die Zahl mit der magischen Zahl 0x55555556 multipliziert werden, und die oberen 32 Bits des Ergebnisses sind, was wir suchen. Zum Beispiel kann die folgende C-Code:

int32_t div3(int32_t x) 
{ 
    return x/3; 
} 

mit GCC kompiliert und -O2, ergibt dies:

08048460 <div3>: 
8048460: 8b 4c 24 04    mov ecx,DWORD PTR [esp+0x4] 
8048464: ba 56 55 55 55   mov edx,0x55555556 
8048469: 89 c8     mov eax,ecx 
804846b: c1 f9 1f    sar ecx,0x1f 
804846e: f7 ea     imul edx 
8048470: 89 d0     mov eax,edx 
8048472: 29 c8     sub eax,ecx 
8048474: c3      ret 

Ich vermute, die sub Anweisung ist verantwortlich für negative Zahlen Festsetzung, weil das, was sie tut ist im Wesentlichen 1, wenn das Argument negativ ist, und es ist ansonsten ein NOP.

Aber warum funktioniert funktioniert das? Ich habe versucht, kleinere Zahlen manuell mit einer 1-Byte-Version dieser Maske zu multiplizieren, aber ich sehe kein Muster, und ich kann nirgendwo wirklich Erklärungen finden. Es scheint eine geheimnisvolle magische Zahl zu sein, deren Herkunft niemandem klar ist, genau wie 0x5f3759df.

Kann jemand eine Erklärung für die Arithmetik liefern?

Answer 1

Es ist, weil 0x55555556 ist wirklich 0x100000000/3, aufgerundet.

Die Rundung ist wichtig. Da sich 0x100000000 nicht gleichmäßig durch 3 teilt, wird ein Fehler im vollständigen 64-Bit-Ergebnis auftreten. Wenn dieser Fehler negativ wäre, wäre das Ergebnis nach dem Abschneiden der unteren 32 Bits zu niedrig. Durch das Aufrunden ist der Fehler positiv, und es ist alles in den unteren 32 Bits, so dass die Trunkierung es auslöscht.