Perché il 0x55555556 si divide per 3 hack?

Question

Esiste un hack (relativamente) ben noto per dividere un numero di 32 bit per tre. Invece di usare la divisione attuale costoso, il numero può essere moltiplicato per il numero magico 0x55555556, e la parte superiore 32 bit del risultato sono ciò che stiamo cercando. Ad esempio, il seguente codice C:

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

compilato con GCC e -O2, risultati in questo:

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 

sto cercando di indovinare le istruzioni sub è responsabile per fissare i numeri negativi, perché ciò che fa è essenzialmente aggiungere 1 se l'argomento è negativo, ed è un NOP altrimenti.

Ma perché fa questo lavoro? Ho cercato di moltiplicare manualmente i numeri più piccoli con una versione a 1 byte di questa maschera, ma non riesco a vedere uno schema, e non riesco a trovare alcuna spiegazione da nessuna parte. Sembra essere un numero magico mistero la cui origine non è chiara a nessuno, proprio come 0x5f3759df.

Qualcuno può fornire una spiegazione della aritmetica dietro questo?

Answer 1

È perché 0x55555556 è davvero 0x100000000/3, arrotondato per eccesso.

L'arrotondamento è importante. Poiché 0x100000000 non si divide uniformemente per 3, si verificherà un errore nel risultato completo a 64 bit. Se quell'errore fosse negativo, il risultato dopo il troncamento dei 32 bit inferiori sarebbe troppo basso. Arrotondando, l'errore è positivo, ed è tutto nei 32 bit inferiori, quindi il troncamento lo cancella.