Bit Manipulation

High-level programmers manipulate objects. Systems programmers manipulate bits. This is used for packing data (network protocols), interacting with hardware registers (drivers), and extreme optimization.

Mastering Shifts (<<, >>)

Move bits left or right.

• x << k: Bits move left. 0s fill the right. Equivalent to multiply by $2^k$.
• x >> k: Bits move right.
  • Unsigned (Logical): 0s fill the left.
  • Signed (Arithmetic): Sign bit fills the left. (Preserves negative numbers).

The "1 << k" Idiom

1 << k creates a “mask” with a single 1 at position k. 1 << 2 $\to$ 0000 0100.

The Standard Idioms (Memorize These)

Let x be your variable and k be the bit position (0-31).

1. Set a Bit (Turn ON)

You want to force bit k to be 1. Use OR with a mask.

x = x | (1 << k);
// x |= (1 << k);

Logic: Anything | 1 = 1. Anything | 0 = Anything.

2. Clear a Bit (Turn OFF)

You want to force bit k to be 0. Use AND with an inverted mask.

x = x & ~(1 << k);
// x &= ~(1 << k);

Logic: Mask is 1111 1011. Anything & 0 = 0. Anything & 1 = Anything.

3. Toggle a Bit (Flip)

You want 0 $\to$ 1 and 1 $\to$ 0. Use XOR.

x = x ^ (1 << k);
// x ^= (1 << k);

Logic: 0 ^ 1 = 1. 1 ^ 1 = 0.

4. Check a Bit

Is bit k ON? Mask it and check if the result is non-zero.

if ((x & (1 << k)) != 0) { ... }
// Alternative: shift it down to position 0
if ((x >> k) & 1) { ... }

Advanced Tricks (The “Kernel” Hacks)

• Power of 2 Check: x & (x - 1) == 0. Trick: x-1 flips all trailing 0s and the lowest 1. ANDing them kills the only 1 bit if it was a power of 2.

  • 1000 (8) & 0111 (7) = 0000.

• Isolate Lowest Set Bit: x & -x. Trick: Two’s complement (-x) is ~x + 1. The carry ripples up to the first set bit.

  • 0110 (6) & 1010 (-6) = 0010.

• Turn Off Lowest Set Bit: x & (x - 1). Use: Loop this to count number of set bits (population count) faster than scanning all 32 bits.

• Modulo $2^k$: x & (n - 1).

  • x % 32 is just x & 31. Much faster than div/mod instructions.

• XOR Swap: x ^= y; y ^= x; x ^= y;

Practice: Packet Decoding

Imagine a network packet header: 0xFA32 (1111 1010 0011 0010)

• Top 4 bits: Version
• Next 4 bits: Header Length

Start: unsigned int header = 0xFA32;

Extract Version:

1. We want the top 4 bits (F).
2. Shift right by 12. header >> 12 $\to$ 0x000F.
3. Mask with 0xF (optional here since we shifted zeros in, but safe).
4. Result: 15 (Version 15).

Extract Header Length:

1. We want the second nibble (A).
2. Shift right by 8. header >> 8. Result is 0x00FA.
3. Mask with 0xF to erase the F. 0xFA & 0xF.
4. Result: 0xA (Length 10).