There is a (relatively) well known hack for dividing a 32-bit number by three. Instead of using actual expensive division, the number can be multiplied by the magic number 0x55555556, and the upper 32 bits of the result are what we're looking for. For example, the following C code:
int32_t div3(int32_t x)
{
return x / 3;
}
compiled with GCC and -O2, results in this:
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
I'm guessing the sub instruction is responsible for fixing negative numbers, because what it does is essentially add 1 if the argument is negative, and it's a NOP otherwise.
But why does this work? I've been trying to manually multiply smaller numbers by a 1-byte version of this mask, but I fail to see a pattern, and I can't really find any explanations anywhere. It seems to be a mystery magic number whose origin isn't clear to anyone, just like 0x5f3759df.
Can someone provide an explanation of the arithmetic behind this?