vogel's blog

By vogel, 7 years ago, translation,

Now I am writing an article about bit manipulation, bit magic and other trciks for wiki — conspects (This is a great resource of algorithms in Russian). If you know some useful bit tricks, which used in algoritms or just funny things connected with bits write them in comments below. Also you are welcomed with really strange, weird and sophisticated solutions for well-known problems. For example: swapping values with XOR.

• Descripotion of the problem
• Solution of the problem in code with short explanation for tricky moments

Example of a perfect comment:
Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here

f = (v & (v - 1)) == 0;


Short explanation: Let v — power of two (this is one and k zeros in binary presentation) and v — 1 is k ones in binary presenation. Then notice that bitwise AND v and v — 1 must be 0.

Warm — up problem: Find smallest 1 — bit (not zero) in O(1)