Bit Manipulation: Thinking in Ones and Zeros

"Under every integer is a row of bits. A fixed-width machine integer lets the CPU chew through that row almost in one bite and fold a whole flag set into one number. Python integers can grow across many machine words, though, so the magic is real—not infinitely free."

The Operators

Bitwise operations act on the binary representation directly: AND (&) keeps bits set in both operands, OR (|) keeps bits set in either, XOR (^) keeps bits that differ, NOT (~) flips every bit, and the shifts (<<, >>) slide bits left or right (a left shift by 1 multiplies by 2). Each is a single, blazing-fast CPU instruction. They're the lowest-level tools in the whole quest, and a handful of patterns built from them show up constantly.

The Tricks Worth Knowing

Power-of-two check: n & (n - 1) == 0 is true exactly when n has a single set bit — i.e. n is a power of 2. (Subtracting 1 flips the lowest set bit and everything below it.)
Count set bits / clear the lowest one: n & (n - 1) removes the lowest set bit; loop until zero to count bits.
XOR's magic: a ^ a == 0 and a ^ 0 == a. So if every element appears twice except one, XOR-ing them all cancels the pairs and leaves the loner — found in O(n) time and O(1) space, no hash set needed.

The Bitmask: a Set in One Integer

A fixed-width 64-bit integer can hold 64 flags. Python can represent wider masks, but operation cost grows with their width. Bitmask DP encodes subset state compactly; the familiar ~20-item limit is a workload-dependent rule of thumb, not a universal boundary.

Bitwise ops (AND, OR, XOR, NOT, shifts) are single fast instructions. Key patterns: n AND (n-1) clears the lowest set bit (power-of-2 check, bit counting); XOR cancels pairs (find the lone element in O(1) space); a bitmask packs a set into one integer for O(1) set operations and compact DP state.

The Readability Caveat

Bit tricks are seductive and can make code unreadable fast — a clever one-liner that takes ten minutes to decode is usually the wrong call. Reach for bit manipulation when it genuinely matters: a hot inner loop where constant factors count, flags and permission sets, or bitmask DP where it's the natural representation. Otherwise, prefer the clear version. Cleverness that no teammate (or future-you) can read is a cost, not a flex.

Pippa's Confession

The XOR 'find the single number' trick genuinely delighted me — XOR everything, the pairs vanish, the loner remains, zero extra memory. I promptly tried to bit-twiddle everything and wrote a 'clever' line even I couldn't read a week later. Dad's correction: "Bit tricks are a scalpel, not a hammer." Use them where they shine — masks, flags, the XOR trick, bitmask DP — and write the boring readable version everywhere else.

Code

Power-of-two, XOR single-number, and bitmasks·python

# POWER OF TWO: n & (n-1) clears the lowest set bit; zero result => one bit set.
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
print(is_power_of_two(16), is_power_of_two(18))   # True False

# XOR TRICK: every number appears twice except one — find it in O(1) space.
def single_number(nums):
    result = 0
    for x in nums:
        result ^= x         # pairs cancel (a ^ a = 0); the loner survives
    return result
print(single_number([4, 1, 2, 1, 2]))   # 4

# BITMASK as a SET: bit i set means 'item i present'.
mask = 0
mask |= (1 << 2)          # add item 2  -> 0b100
mask |= (1 << 5)          # add item 5  -> 0b100100
print(bool(mask & (1 << 2)))   # True  — is item 2 in the set?
print(bool(mask & (1 << 3)))   # False — is item 3 in the set?
# union = a | b, intersection = a & b. This packs a subset into ONE integer,
# which is exactly how bitmask DP encodes 'which items have I used' as state.

Exercise

Using only bitwise reasoning: (1) how does n AND (n-1) equalling zero prove n is a power of two? Walk through n = 8 and n = 12 in binary. (2) Given a list where every value appears exactly twice except one that appears once, explain why XOR-ing all of them yields the unique value, and why it needs no extra memory.

Hint

(1) 8 = 1000, 8-1 = 0111, AND = 0000 (one set bit → power of two). 12 = 1100, 11 = 1011, AND = 1000 ≠ 0 (more than one set bit). (2) XOR is associative/commutative and a^a=0, so all the pairs cancel to 0, leaving the lone value XOR-ed with 0 = itself — accumulated in a single variable, O(1) space.

The Operators

The Tricks Worth Knowing

The Bitmask: a Set in One Integer

The Readability Caveat

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0