Chapter 23 — Bit Manipulation

Chapter 23 — Bit Manipulation

Hey everyone! Welcome back to Namaste DSA!

Deep down, everything in a computer is 1s and 0s. Bit manipulation lets you work at that level for tricks that are blazing fast and use almost no memory. A few operators unlock clever solutions that look like magic — like finding a unique number in O(n) time and O(1) space.

What we will cover:

• Binary number basics
• The operators: AND, OR, XOR, NOT, shifts
• XOR tricks (find the single number)
• Check / set / clear a bit
• Counting set bits
• Interview Questions

---

1. Binary Basics

┌─────────────────────────────────────────────────────────────┐
│   Each bit is a power of 2 (right to left):                 │
│                                                             │
│      1   0   1   1   (binary)                               │
│      8   4   2   1   (place values)                         │
│      8 + 0 + 2 + 1 = 11 (decimal)                          │
│                                                             │
│   13 in binary = 1101                                       │
└─────────────────────────────────────────────────────────────┘

---

2. The Operators

Operator	Symbol	Rule	Example
AND	&	1 only if BOTH are 1	1100 & 1010 = 1000
OR	|	1 if EITHER is 1	1100 | 1010 = 1110
XOR	^	1 if bits DIFFER	1100 ^ 1010 = 0110
NOT	~	flip every bit	~1100 = ...0011
Left shift	<<	×2 per shift	0011 << 1 = 0110
Right shift	>>	÷2 per shift	0110 >> 1 = 0011

HANDY SHORTCUTS:
  x << 1   →  multiply by 2
  x >> 1   →  divide by 2 (floor)
  x & 1    →  is x odd?  (1 = odd, 0 = even)
  1 << k   →  the number with only bit k set (a "mask")

---

3. XOR — The Star of the Show

┌─────────────────────────────────────────────────────────────┐
│            XOR's MAGIC PROPERTIES                            │
├─────────────────────────────────────────────────────────────┤
│   x ^ 0 = x          (XOR with 0 = unchanged)               │
│   x ^ x = 0          (a number XOR itself = 0)              │
│   XOR is commutative & associative (order doesn't matter)   │
└─────────────────────────────────────────────────────────────┘

Find the single number: every element appears twice except one. XOR them all — pairs cancel to 0, leaving the unique one!

function singleNumber(nums) {
    let result = 0;
    for (const n of nums) result ^= n;   // pairs cancel out
    return result;
}

HAND TRACE: singleNumber([4, 1, 2, 1, 2])
  0 ^ 4 = 4
  4 ^ 1 = 5
  5 ^ 2 = 7
  7 ^ 1 = 6
  6 ^ 2 = 4      ← the 1s and 2s cancelled, 4 remains ✔
  O(n) time, O(1) space — no hash map needed!

---

4. Check / Set / Clear a Bit

// Is bit k set?  (returns 0 or non-zero)
const isSet = (x, k) => (x >> k) & 1;

// Set bit k to 1
const setBit = (x, k) => x | (1 << k);

// Clear bit k to 0
const clearBit = (x, k) => x & ~(1 << k);

// Toggle bit k
const toggleBit = (x, k) => x ^ (1 << k);

EXAMPLE: set bit 1 of 1001 (=9)
  1 << 1 = 0010 (the mask)
  1001 | 0010 = 1011 = 11 ✔

---

5. Counting Set Bits (Brian Kernighan's Trick)

Count how many 1s are in a number. The trick x & (x - 1) removes the lowest set bit each time — so you loop only as many times as there are 1s.

function countBits(x) {
    let count = 0;
    while (x) {
        x &= (x - 1);     // drop the lowest set bit
        count++;
    }
    return count;
}

HAND TRACE: countBits(11) → binary 1011
  x=1011, x&(x-1)=1010, count=1
  x=1010, x&(x-1)=1000, count=2
  x=1000, x&(x-1)=0000, count=3
  x=0 → stop → 3 ones ✔

---

Interview Questions — Quick Fire!

Q: What are the key properties of XOR?

"x XOR 0 is x, x XOR x is 0, and it's commutative and associative so order doesn't matter. These let pairs cancel out, which is why XOR-ing a list where every number appears twice except one leaves exactly the unique number."

Q: How do you find the single non-duplicated number in O(1) space?

"XOR all the elements together. Every number that appears twice cancels itself to zero, and XOR with zero leaves the value unchanged, so the result is the single number. It's O(n) time and O(1) space — better than a hash map."

Q: How do you check, set, and clear a specific bit?

"Check bit k with (x >> k) & 1. Set it with x | (1 << k). Clear it with x & ~(1 << k). Toggle it with x ^ (1 << k). The expression (1 << k) is a mask isolating bit k."

Q: How does x & (x - 1) help count set bits?

"Subtracting one flips the lowest set bit and all the zeros below it, so ANDing with the original clears exactly that lowest set bit. Repeating until x is zero runs once per set bit, so counting is O(number of 1s) rather than O(total bits)."

Q: What's a fast way to check if a number is a power of two?

"A power of two has exactly one set bit, so x > 0 && (x & (x - 1)) === 0. The trick clears the only set bit, giving zero precisely when there was exactly one."

---

Quick Recap

Concept	Key Takeaway
Operators	& OR ^ ~ << >>.
x & 1	Odd/even check.
XOR	x^x=0, x^0=x → pairs cancel.
Single number	XOR all → O(n), O(1).
1 << k	Mask for bit k (check/set/clear).
x & (x-1)	Drops lowest set bit → count 1s.

What's Next?

The final chapter! Chapter 24: Math for DSA — GCD, primes, the Sieve, modular arithmetic, and fast exponentiation — the little math toolkit that unlocks a surprising number of problems.

Keep coding, keep grinding! See you in the next one!