Bit Manipulation

Why this module exists

Bits are the closest you can get to the metal. Many problems become simple once you reason one bit at a time. You will see bit tricks in arrays, math, DP, and systems.

Key idea: represent numbers as binary and use bitwise operators to test, set, and combine information quickly.

---

Core operators

• & AND: keeps bits that are 1 in both numbers
• | OR: keeps bits that are 1 in either number
• ^ XOR: keeps bits that are different
• ~ NOT: flips all bits
• << and >>: shift left/right by powers of two

Remember: x ^ x = 0 and x ^ 0 = x.

---

XOR cancels duplicates

If every value appears twice except one, XOR of the whole array leaves the unique value.

func singleNumber(nums []int) int {
    ans := 0
    for _, n := range nums {
        ans ^= n
    }
    return ans
}

---

Set-bit tricks

Two extremely useful identities:

• n & (n - 1) clears the lowest set bit
• n & -n isolates the lowest set bit (two's complement)

Counting set bits is just repeated clearing:

count := 0
for n != 0 {
    n &= n - 1
    count++
}

---

Bitwise AND on a range

The AND of a range keeps only the common prefix of all numbers. Shift both ends right until they match, then shift back.

---

Per-bit reasoning

For a | b == c, decide flips independently per bit:

• If c has 0, both a and b must be 0 (flip any 1s)
• If c has 1, at least one of a or b must be 1

---

Maximum XOR pair

Build the result from the top bit down. At each bit, ask: "Can any two prefixes reach this candidate?"

This greedy + prefix-set approach runs in O(32n).

---

What you will build

• Find the single non-duplicated value with XOR.
• Check whether a number is a power of two.
• Count set bits efficiently.
• Compute range AND via common prefixes.
• Flip bits to satisfy an OR constraint.
• Maximize XOR over any pair.