Basic Bit Manipulation
Symbols
| Symbol | Description |
|---|---|
| & | AND |
| | | OR |
| ^ | XOR |
| ~ | NOT |
| X | Y | X&Y | X|Y | X^Y | ~X |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Magic of XOR
Here's are some magic of XOR.[1]
XOR:
0 if the inputs are the same, 1 if the inputs are different.
x ^ 0 = x
x ^ 1 = ~x // 1 = ~0
x ^ (~x) = 1
XOR Itself
x ^ x = 0
XOR Swapping
a ^ b = c => a ^ c = b => b ^ c = a
XOR Associative
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
Shift Operation
shift operation can be considered as multiple with 2 or divided by 2. For example,
0b0110 * 0b0010 is equals to 0b0110 << 2
Set the rightmost n bits of x to zero
e.g. b0001111 to b0001100 when n = 2
x & (~0 << n)
Get the nth bit value
x & (1 << n)
Only set nth bit to 1
x |= (1 << n)
Only set nth bit to 0
x &= ~(1 << n)
Advanced Operations
Clear from the highest bit to the nth bit of x
including nth bit
x & ((1 << n) - 1)
Clear from the nth bit to the 0th bit of x
including nth bit
x & ~(1 << (n+1))
Only update the nth bit to the value v
if v is 1, then update to 1; otherwise to 0;
mask = ~(1 << n);
x = (x & mask) | (v << 1)