Formulas are given in C/C++, which uses two's complemet
Beginner level
x = (1 << y) ^ x — toggle a bit.
x = (1 << y) | x — addding a bit.
x = ~(1 << y) & x — removing a bit.
if (1 << y & x) — check whether y-th bit is set.
Intermediate level
-x = ~x + 1 — negative $$$ x $$$ in two's complement representation.
x & (-x) — least significant bit, LSB
if (x && !((x-1) & x) — check whether x is a power of two
Complex level
Bit swap
p = ((x >> a) ^ (x >> b)) & 1
x ^= (p << a)
x ^= (p << b)
Number of set bits
aka population count. x = x & (x-1) removes least significant bit, Brian Kernighan method.
for (c = 0; x; c++)
x = x & (x-1)
Swapping values
b ^= a ^= b;
a ^= b;
All submasks of mask
Excluding blank mask. Also, enumerating all masks and their submasks is $$$ O(3^n) $$$.
for (int s = m; s; s = (s-1)&m)
//do something
Bit scan forward
BSF, null indexed position of LSB. $$$ x $$$ should not be zero.
x = x & (-x);
int pos = 0;
if (x & 0xffff0000) pos += 16;
if (x & 0xff00ff00) pos += 8;
if (x & 0xf0f0f0f0) pos += 4;
if (x & 0xcccccccc) pos += 2;
if (x & 0xaaaaaaaa) pos += 1;
Next permutation
Rearranges bit set of number into the lexicographically next greater permutation.
t = x | (x - 1);
x = (t + 1) | (((~t & -~t) - 1) >> (BSF(v) + 1));
Summary
Most of these are useless or can be replaced with builtin functions, but if some of you find them intersting you should check out this list or this video.
