Pattern #34

Bit Manipulation

Important interview questions, thinking patterns, XOR cancellation, Kernighan's bit counting, Subsets bitmasking, Go operators, and interview rules.

Must Solve

16 core questions — solve these first.

1.Single Number
XOR all numbers: x ^ x = 0 and x ^ 0 = x. Unique number remains in O(N) time & O(1) spaceeasy
2.Number of 1 Bits
Brian Kernighan: loop n = n & (n - 1) until n == 0easy
3.Counting Bits
DP: ans[i] = ans[i >> 1] + (i & 1)easy
4.Reverse Bits
Loop 32 bits: result = (result << 1) | (n & 1); n >>= 1easy
5.Power of Two
Check n > 0 && (n & (n - 1)) == 0easy
6.Missing Number
XOR all numbers 0..N with array elements: duplicates cancel outeasy
7.Single Number II
Bit counting: For each bit position sum % 3 gives unique bitmedium
8.Single Number III
XOR all = a ^ b. Isolate diff bit = xor & -xor to partition into 2 groupsmedium
9.Bitwise AND of Numbers Range
Right shift left & right until equal (find common binary prefix)medium
10.Sum of Two Integers
Adder logic without +: sum = a ^ b, carry = (a & b) << 1medium
11.Minimum Bit Flips to Convert Number
Count set bits of start ^ goaleasy
12.Hamming Distance
Count set bits of x ^ yeasy
13.Find the Difference
XOR all chars of s and teasy
14.Maximum XOR of Two Numbers in an Array
Bit Trie: insert binary numbers and greedily choose opposite bitmedium
15.Subsets Using Bitmask
Loop mask from 0 to (1 << N) - 1: bit i set means include element imedium
16.Maximum Product of Word Lengths
Convert words to 26-bit bitmasks + compare masks (m1 & m2 == 0)medium

Also Important

9 more questions worth practicing.

17.Power of Four
Power of 2 check + (n & 0x55555555) != 0 (odd position bit)easy
18.Binary Number with Alternating Bits
Check (n ^ (n >> 1)) & ((n ^ (n >> 1)) + 1) == 0easy
19.Complement of Base 10 Integer
Create bitmask of all 1s matching length of n, return mask ^ neasy
20.Count Triplets That Can Form Two Arrays of Equal XOR
Prefix XOR array: if pref[i] == pref[k+1], all j in between workmedium
21.XOR Queries of a Subarray
Prefix XOR array: query(L, R) = pref[R+1] ^ pref[L]medium
22.Decode XORed Array
Reconstruct: arr[i+1] = encoded[i] ^ arr[i]easy
23.Gray Code
N-bit Gray Code formula: g(i) = i ^ (i >> 1)medium
24.Bitwise ORs of Subarrays
HashSet maintaining active subarray OR valuesmedium
25.Minimum Flips to Make a OR b == c
Bitwise check for each bit position of a, b, cmedium

How to Think

Need check one flag quickly?Bit Mask (n & (1 << i))
Every number appears twice except one?XOR (x ^ x = 0, x ^ 0 = x)
Need know if bit i is ON?AND (n & (1 << i) != 0)
Need turn bit ON?OR (n | (1 << i))
Need toggle a bit?XOR (n ^ (1 << i))
Need turn bit OFF?AND NOT (n &^ (1 << i) in Go)
Need all subsets and N is small?Bitmask (loop 0 to 2^N - 1)

Go Bit Manipulation Code Templates

Core Bitwise Operators in Go

// Check if bit i is set (ON)
func isBitSet(n int, i int) bool {
    return (n & (1 << i)) != 0
}

// Set bit i (turn ON)
func setBit(n int, i int) int {
    return n | (1 << i)
}

// Clear bit i (turn OFF using Go AND NOT &^ operator)
func clearBit(n int, i int) int {
    return n &^ (1 << i)
}

// Toggle bit i
func toggleBit(n int, i int) int {
    return n ^ (1 << i)
}

// Remove lowest set bit (Brian Kernighan)
func dropLowestSetBit(n int) int {
    return n & (n - 1)
}

👉 Go special clear operator: &^ (AND NOT)!

Core Operators & Essential Bit Tricks

1. Power of Two Check

A power of two has exactly one set bit in binary: n > 0 && (n & (n - 1)) == 0.

2. Count Set Bits (Kernighan)

Looping n = n & (n - 1) drops the lowest set bit in each step, completing in O(set_bits) time!

3. Isolate Lowest Set Bit

diff = n & -nisolates the rightmost 1-bit in two's-complement representation (used in Single Number III & Fenwick Tree).

4. Hamming Distance

Number of differing bits between x and y is simply the set bit count of x ^ y.

Subsets Bitmasking Generation (O(2^N))

When N <= 15, every subset corresponds to an integer mask from 0 to (1 << N) - 1:

func subsets(nums []int) [][]int {
    n := len(nums)
    total := 1 << n // 2^N subsets
    result := make([][]int, 0, total)

    for mask := 0; mask < total; mask++ {
        curr := []int{}
        for i := 0; i < n; i++ {
            if (mask & (1 << i)) != 0 {
                curr = append(curr, nums[i])
            }
        }
        result = append(result, curr)
    }
    return result
}

Visual Memory Rule

AND (&)        → Check if bit is set
OR (|)         → Set bit (turn ON)
XOR (^)        → Toggle bit / Cancel equal pairs (x^x=0)
AND NOT (&^)   → Clear bit (turn OFF in Go)
n & (n - 1)    → Drop lowest 1 bit
n & -n         → Isolate lowest 1 bit

💡 Golden Rule: "Think of an integer as a row of tiny ON/OFF switches, and use bit operators to control those switches directly."

Common Interview Mistakes

1. Confusing OR and XOR

Remembering 1 | 1 = 1 (OR sets both) vs 1 ^ 1 = 0 (XOR cancels duplicates!).

2. Wrong 1-Based Bit Position

Bit positions are 0-indexed! The rightmost LSB is bit 0 (1 << 0 = 1).

3. Forgetting Operator Parentheses

Writing n & 1 << i == 0 instead of (n & (1 << i)) == 0 due to lower operator precedence!

4. Using XOR Without Pair Guarantee

XOR cancellation x ^ x = 0 only works when duplicates appear an EVEN number of times! (For 3 times use bit counting).

Interview Rules

1. Duplicate pairs + one unique? → XOR (x ^ x = 0)
2. Check bit i? → (n & (1 << i)) != 0
3. Set bit i? → n | (1 << i)
4. Toggle bit i? → n ^ (1 << i)
5. Clear bit i in Go? → n &^ (1 << i)
6. Count set 1-bits? → Brian Kernighan (n & (n - 1))
7. Subsets for small N? → Bitmask loop from 0 to (1 << N) - 1
8. Maximum XOR of array pairs? → Bit Trie (choose opposite binary bit high to low)

Small Rules

Rule 1: XOR of identical values cancels to 0 (x ^ x = 0, x ^ 0 = x).
Rule 2: Always wrap bitwise expressions in explicit parentheses to avoid precedence errors.
Rule 3:n & (n - 1) clears the rightmost set 1-bit.
Rule 4:n & -n isolates the rightmost set 1-bit.
Rule 5:Go uses the &^ (AND NOT) operator for bit clearing.

Production Thinking

RBAC / Unix Bitwise Permissions → Store READ=1, WRITE=2, DELETE=4, ADMIN=8 in single integer bitmap

Feature Flag Compact Packing → Pack 32/64 boolean feature flags into single uint64 bitmask

Network Protocol Flag Headers → Read TCP ACK, SYN, FIN flags via bitwise AND masks

Hardware / Embedded Registers → Directly control hardware device status registers via bit manipulation

Remember This

AND         → Check
OR          → Set
XOR         → Toggle / cancel duplicates
AND NOT     → Clear (&^ in Go)
x ^ x       → 0
x ^ 0       → x
n & (n-1)   → Remove lowest set bit
Power of 2  → n > 0 && (n & (n-1)) == 0
Subsets     → Bitmask 0..2^N-1

💡 Golden Rule: "Think of an integer as a row of tiny ON/OFF switches, and use bit operators to control those switches directly."