These are some binary tricks that I collected on the web. Useful or not. Some of them are the reinventing-the-wheel product of mine. But it is nice to keep a record here.
Return right-most bit
Return right-most bit set, either one:
x & -x
x & (~x + 1)
Return right-most bit unset:
~x & (x + 1)
By the similar logic, the increment and decrement can be done bitwise:
x = -(~x); // x++
x = ~(-x); // x--
And also doing negation:
x = (~x)+1; // x = -x
x = (x ^ -1)+1; // x = -x
So we also have the following two ways to do absolute value (assume integer of 32-bit):
(x ^ (x>>31)) - (x>>31) // (x>0)?x:-x
(x ^ (x>>31)) + (unsigned(x)>>31)
Comparing integers of equal sign
if ((a ^ b) >= 0) // Same as a*b > 0
But note, when any of the two integer is zero, the construct is not exactly equal: In this case, zero is treated as positive.
Even/Odd check
if ((a & 1) == 0) // Same as a%2 == 0
Reset the right-most bit
Right-most set-bit become unset
x & (x - 1)
We can check if a positive number is a power of 2 by verifying x & (x-1) == 0
. Alternative ways to check is x & -x == x
.
Get the next power of 2
Simply speaking, find the MSB set, and left shift by 1. The key idea below is to set all bits after the MSB set, then increment it.
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
x++;
But the above code will convert a power of 2 to the next power of 2 rather than
staying there. Thus it is not “rounding” to next power of 2 exactly. To do
rounding, i.e. not modifying the value if it is already a power of 2, do a x--
first.
Tell the position of the right-most set bit
popcount(x ^ (x-1))
Reverse bits
x = ((x>>1) & 0x55555555) | ((x<<1) & 0xAAAAAAAA);
x = ((x>>2) & 0x33333333) | ((x<<2) & 0xCCCCCCCC);
x = ((x>>4) & 0x0F0F0F0F) | ((x<<4) & 0xF0F0F0F0);
x = ((x>>8) & 0x00FF00FF) | ((x<<8) & 0xFF00FF00);
x = ((x>>16)& 0x0000FFFF) | ((x<<16)& 0xFFFF0000);
Rounding
If we want to round a number x
to the lower multiple of y
(i.e. round down), we can do this:
int x;
x = (int)(x/y)*y;
To round to the upper multiple of y
(i.e. round up), it is:
x = (int)((x+y-1)/y)*y;
To round off, i.e. to the nearest multiple of y
, it is:
x = (int)((x+y/2)/y)*y;
Guarantee a positive/negative value
For an integer x
, make it zero if it is positive/negative and leave it
untouched otherwise. To make sure it is non-positive, mask it with 0 if its MSB
is 0:
x &= x >> 31;
To make sure it is non-negative, mask it with 0 if its MSB is 1:
x &= (~x) >> 31;
Identities
x + y == (x & y) + (x | y)
x | y == (x ^ y) + (x & y)
More: