Bitwise hacks
From VT.Prog
Contents |
Modulus
If your program involves modular arithmetic, try to write the code so that the modulus will be a power of 2. Then, you can substitute with a more efficient operation.
// old: int result = x % 16; // new: int result = x & 15;
On intel x86, this results in
; %eax = input old: movl %eax, %edx sarl $31, %eax xorl %eax, %edx subl %eax, %edx andl $15, %edx xorl %eax, %edx movl %edx, %ecx subl %eax, %ecx movl %ecx, %eax new: andl $15, (%eax)
Division
Likewise, multiplication and division by powers of two can be replaced with bitshifts.
// old: int result = x / 128; // new: int result = x >>= 7;
On intel x86, this results in
; %eax = input old: movl %eax, %edx sarl $31, %eax andl $127, %eax addl %edx, %eax sarl $7, %eax new: sall $7, (%eax)
Rounding
Round up to the next power of two.
inline int ceil2(int x)
{
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x++;
return x;
}
Swapping
A nice xor hack.
#define SWAP(x,y) ( ((x)^=(y)) , ((y)^=(x)) , ((x)^=(y)) )
Order of 2 Checking
A nice way to check if an unsigned integer is an order of 2.
(x & (~x + 1)) == x
