Bit Manipulation: The Operators, the Tricks, and When Bits Beat Data Structures

Underneath every data type, values are bits — and operating on those bits directly is sometimes far faster and more elegant than any higher-level structure. Bit manipulation is a smaller topic than the paradigms before it, but it delivers a distinctive payoff: replacing a set with a single integer, testing membership in O(1), or solving a problem with no auxiliary memory. This lesson covers the operators, the classic tricks worth memorizing, and when reaching for bits actually pays off.

In plain words — light switches

Think of each bit as a light switch: 1 is on, 0 is off. AND is 'both switches must be on'. OR is 'either switch on'. XOR is 'exactly one on (they differ)'. NOT flips every switch. Shifting left doubles the value — like moving a number one column left in decimal. Shifting right halves it. At hardware level these are single CPU instructions, which is why bit operations can outperform even simple data structures: no allocation, no indirection, no cache miss — just a register.

The operators

A  B | A & B | A | B | A ^ B
─────┼───────┼───────┼───────
0  0 |   0   |   0   |   0
0  1 |   0   |   1   |   1
1  0 |   0   |   1   |   1
1  1 |   1   |   1   |   0

Key pattern: XOR is 1 only when bits DIFFER.
             XOR with itself always gives 0  (a ^ a = 0).
             XOR with 0 leaves a bit unchanged (a ^ 0 = a).

Value 12:  0 0 0 0 1 1 0 0    (= 12)
                   7 6 5 4 3 2 1 0   ← bit positions

12 << 1:   0 0 0 1 1 0 0 0    (= 24)   × 2
12 << 2:   0 0 1 1 0 0 0 0    (= 48)   × 4
12 >> 1:   0 0 0 0 0 1 1 0    (= 6)    ÷ 2
12 >> 2:   0 0 0 0 0 0 1 1    (= 3)    ÷ 4

Left shift by k  → multiply by 2ᵏ  (if no overflow).
Right shift by k → integer divide by 2ᵏ (for non-negative).

Two of these encode arithmetic: x << k multiplies x by 2ᵏ and x >> k divides by 2ᵏ (for non-negative x). XOR is the star of algorithmic tricks because of its self-canceling property (a ^ a = 0). A caution: shifts and NOT interact with sign bits and integer width in language-specific ways — signed right shift, overflow on left shift — so know your language's rules on bit width and signedness before relying on them.

The essential bit tricks

• Check bit i: (x >> i) & 1 — is the i-th bit set? (Or x & (1 << i) is nonzero.)
• Set bit i: x | (1 << i) — force the i-th bit to 1.
• Clear bit i: x & ~(1 << i) — force the i-th bit to 0.
• Toggle bit i: x ^ (1 << i) — flip the i-th bit.
• Is x a power of two? x > 0 and (x & (x − 1)) == 0. A power of two has exactly one set bit; subtracting 1 flips that bit and all zeros below it, so the AND is 0. Elegant and O(1).
• Remove the lowest set bit: x & (x − 1). Repeatedly doing this until x is 0 counts the set bits (Brian Kernighan's algorithm) in O(number of set bits) rather than O(bit width).
• Isolate the lowest set bit: x & (−x).

x = 44:  0 0 1 0 1 1 0 0   (bits 5, 3, 2 are set)

Check bit 3:    (44 >> 3) & 1  = 5 & 1 = 1  ← bit 3 is set ✓
Set bit 1:       44 | (1<<1)   = 44 | 2 = 46  (0b00101110)
Clear bit 2:     44 & ~(1<<2)  = 44 & ~4 = 40  (0b00101000)
Toggle bit 5:    44 ^ (1<<5)   = 44 ^ 32 = 12  (0b00001100)

Power-of-two test on 32 (0b00100000):
  32 & (32-1) = 32 & 31 = 0b00100000 & 0b00011111 = 0  → IS power of two ✓
Power-of-two test on 44:
  44 & 43 = 0b00101100 & 0b00101011 = 0b00101000 ≠ 0  → NOT power of two

Remove lowest set bit from 44:
  44 & 43 = 0b00101100 & 0b00101011 = 0b00101000 = 40
  (bit 2 removed; next iteration removes bit 3, then bit 5 → 3 iterations = 3 set bits)

The XOR trick, worked step by step

Classic problem: every number in an array appears exactly twice except one — find the loner. Naive approaches use a hash set (O(n) space) or sorting (O(n log n)). The XOR solution: fold the whole array with XOR. Because a ^ a = 0, every duplicated pair cancels to 0, and 0 ^ (unique) = unique.

Step 1: acc = 0
Step 2: acc ^ 4 = 0 ^ 4 = 4
Step 3: acc ^ 1 = 4 ^ 1 = 5         (binary: 100 ^ 001 = 101)
Step 4: acc ^ 2 = 5 ^ 2 = 7         (binary: 101 ^ 010 = 111)
Step 5: acc ^ 1 = 7 ^ 1 = 6         (1 ^ 1 cancels: 111 ^ 001 = 110)
Step 6: acc ^ 2 = 6 ^ 2 = 4         (2 ^ 2 cancels: 110 ^ 010 = 100)

Result: 4  ← the lone element

Why: pairs cancel (1^1=0, 2^2=0), leaving 4^0=4.
Time: O(n). Space: O(1). No hash set, no sort.

XOR also swaps two values without a temp variable (a ^= b; b ^= a; a ^= b) — though a compiler-generated temp is usually just as fast. It also finds a missing number in 0…n: XOR the full range 0…n with every array element; missing values don't cancel and remain.

Bitmasks: an integer as a set

A bitmask uses each bit of an integer as a boolean flag — so a single int represents a subset of up to ~32 or ~64 elements, and set operations become single machine instructions.

Element  Index  Bit value
   A       0      1 << 0 = 001
   B       1      1 << 1 = 010
   C       2      1 << 2 = 100

Set {A, C}  = 001 | 100 = 101  (decimal 5)
Set {B, C}  = 010 | 100 = 110  (decimal 6)

Union  {A,C} ∪ {B,C}  = 101 | 110 = 111  ({A,B,C})
Intersect {A,C} ∩ {B,C} = 101 & 110 = 100  ({C})
Difference {A,C}  {B,C} = 101 & ~110 = 101 & 001 = 001  ({A})
Is B in {A,C}?  5 & (1<<1) = 101 & 010 = 000 → NO
Is C in {A,C}?  5 & (1<<2) = 101 & 100 = 100 → YES

Enumerate all subsets of {A,B,C}:
for mask in 0..7:
  mask=0b000 → {}
  mask=0b001 → {A}
  mask=0b010 → {B}
  mask=0b011 → {A,B}
  mask=0b100 → {C}
  mask=0b101 → {A,C}
  mask=0b110 → {B,C}
  mask=0b111 → {A,B,C}

• Union of two sets: a | b. Intersection: a & b. Difference: a & ~b. Membership of element i: a & (1 << i). All O(1).
• Iterate all subsets of an n-element set: loop a mask from 0 to 2ⁿ − 1; each value's set bits are one subset. This is the enumeration engine behind bitmask dynamic programming (e.g., the traveling-salesman DP over visited-city subsets) and backtracking over small element sets.
• Compact state: representing a board, a set of used columns in N-Queens, or visited nodes as a single integer makes state hashing and comparison trivial and fast.

The constraint: bitmasks only scale to the machine word (~64 elements). For n = 30, iterating all 2³⁰ subsets is a billion operations — feasible but slow; beyond ~n = 40, subset enumeration is infeasible regardless. Bitmasks shine specifically when the element set is *small* (≤ ~20 for exponential algorithms, ≤ ~64 for flag storage).

Common pitfalls

• Signed-shift and overflow surprises. Right-shifting negative numbers, or left-shifting into the sign bit, behaves differently across languages. Use unsigned types or masks when the sign bit is in play.
• Operator precedence. Bitwise operators bind more loosely than comparisons in many languages, so (x & 1 == 0) may parse as x & (1 == 0). Parenthesize generously: write (x & 1) == 0.
• Off-by-one in bit positions. Bits are 0-indexed; the i-th bit is 1 << i, and an n-bit integer's bits run 0…n−1.
• Overusing bit tricks. Clever bit code can be unreadable. Use it where it genuinely helps (hot loops, compact state, elegant XOR solutions), not to show off — a hash set is clearer for most membership needs.
• Assuming bitmasks scale. They cap at the word size; for large sets use a real set or bitset structure, not a single integer.

When to use vs avoid

Practice problems

• Single Number II: Every element appears three times except one (which appears once). XOR alone won't cancel threes — solve in O(n) time, O(1) space using bit-count mod 3 for each bit position.
• Counting Bits: For every integer 0…n, count its set bits. Key insight: bits(x) = bits(x >> 1) + (x & 1) — build iteratively in O(n).
• Maximum XOR of Two Numbers in an Array: Use a trie or bitmask greedy to find the pair that XORs to the maximum value — an elegant problem that combines XOR with trie thinking.

Key takeaways

• Bitwise AND, OR, XOR, NOT, and shifts operate on individual bits; shifts are fast multiply/divide by powers of two.
• XOR's self-canceling property (a ^ a = 0) yields elegant O(1)-space solutions: unique element, missing number, temp-free swap.
• Memorize the check/set/clear/toggle idioms and the power-of-two and lowest-set-bit tricks.
• A bitmask turns an integer into a set: O(1) union/intersection/membership, and subset enumeration for bitmask DP — but only up to word size.
• Bits are a specialist tool: reach for them for compact small-set state and space-free tricks, not as a default over clear data structures.

Next, a deceptively simple structure that made Kruskal's MST fast and answers 'are these connected?' in near-constant time: Union-Find (disjoint set union). Drill bit tricks in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play