Bit Manipulation: Thinking in Ones and Zeros

"Under every integer is a row of bits, and the CPU can twiddle them all at once, in a single instruction. Bit manipulation won't change your algorithm's big-O, but it can shrink constants dramatically and pack a whole set into one number."

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

The biggest idea: a single integer can represent a set of up to ~64 items, where bit i being 1 means 'item i is present.' Then set operations become bit operations — union is OR, intersection is AND, membership is a shift-and-AND, adding an element is OR with a shifted 1. This is compact and fast, and it's the backbone of bitmask DP, where the DP state is 'which subset of items have I used,' encoded as one integer. It's how problems with up to ~20 items and exponential subset-states still fit in memory and run.

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