Bit manipulation, I am no wizard
This post is mainly so I don’t ever lose this information and I have it in a safe place that I can get to from anywhere. Bit manipulation makes me feel like some kind of wizard in a tower when I use it. It conjures images of me as an old man with a giant white bear and crinkly little eyes pouring over giant arcane books of information.
In truth most programmers know that bit manipulation more akin to a peasant flipping some switches. Even so, having those switches flipped at the right moment sure is useful. This was taken orginally in part from http://realtimecollisiondetection.net/blog/?p=78
| Identity | Example | Identity and explanation |
| x | 00101100 | x, the original value |
| ~x | 11010011 | ~x, complement of x |
| -x | 11010100 | -x = ~x+1, negation of x (this you MUST know about 2’s-complement arithmetic!) |
| x & -x | 00000100 | x & -x, extract lowest bit set |
| x | -x | 11111100 | x | -x, mask for bits above (AND including) lowest bit set |
| x ^ -x | 11111000 | x ^ -x, mask for bits above (NOT including) lowest bit set |
| x & (x – 1) | 00101000 | x & (x – 1), strip off lowest bit set |
| x | (x – 1) | 00101111 | x | (x – 1), fill in all bits below lowest bit set |
| x ^ (x – 1) | 00000111 | x ^ (x – 1) = ~x ^ -x, mask for bits below (AND including) lowest bit set |
| ~x & (x – 1) | 00000011 | ~x & (x – 1) = ~(x | -x) = (x & -x) – 1, mask for bits below (NOT including) lowest bit set |
| x | (x + 1) | 00101101 | x | (x + 1), fills in lowest zero bit |
| x / (x & -x) | 00001011 | x / (x & -x), shift number right so lowest bit set ends up at bit 0 |
