Bit Manipulation — Data Structures & Algorithms

Bit manipulation feels like a bag of tricks until you reduce it to one idea: an integer is a compact row of binary switches. The operators let you inspect, combine, and change those switches directly.

Most interview uses are small and sharp: XOR cancels pairs, a mask represents a set, and x & (x - 1) removes the lowest set bit. You do not need to think like a hardware engineer; you need a few identities and the restraint to use them only when they make the solution clearer.

The mental model

Python exposes the standard bitwise operators:

& — AND: bit is 1 only if both inputs have 1.
| — OR: bit is 1 if either input has 1.
^ — XOR: bit is 1 if the inputs differ.
~ — NOT: flips bits, with Python’s signed-integer semantics.
<< — shift left, multiplying by powers of two.
>> — shift right, dividing and discarding low bits for non-negative integers.

A mask isolates one position:

i = 3
mask = 1 << i

x & mask        # check bit i
x | mask        # set bit i
x & ~mask       # clear bit i
x ^ mask        # toggle bit i

Two low-bit idioms are worth memorizing:

x & (x - 1)     # clears the lowest set bit
x & -x          # isolates the lowest set bit

XOR has three properties that solve many “one odd item out” problems:

a ^ a == 0      # a value cancels itself
a ^ 0 == a      # zero changes nothing
a ^ b == b ^ a  # order does not matter

An integer can also act as a tiny set. If bit i is on, item i is included. That makes subset enumeration compact when the universe is small.

Bit manipulation playgroundclick any bit to flip it

180

108

A & B

00100100

A & B — keep bits set in both

bit = 1Bit tricks run in O(1): masks test/set flags, XOR finds the unpaired value, and x & (x-1) clears the lowest set bit.

Pattern recognition

Variations

Worked problems

Try each yourself before revealing the solution. These are small because the identities do the work.

LeetCode 136Easy

Bits
XOR

Single Number

Every integer in an array appears exactly twice except for one integer that appears once. Return the unique integer.

Approach. XOR all numbers together. Every paired value cancels to zero, and XOR is commutative, so the order does not matter. The only value left is the one without a partner.

Show solution

def single_number(nums):
    answer = 0

    for x in nums:
        answer ^= x

    return answer

Complexity. O(n) time and O(1) space. No hash set is needed because XOR stores only the parity of occurrences.

LeetCode 191Easy

Bits
Counting

Number of 1 Bits

Given a non-negative integer, return how many 1 bits appear in its binary representation.

Approach. Repeatedly apply n & (n - 1), which clears the lowest set bit. Each loop removes exactly one 1, so the loop count is the answer.

Show solution

def hamming_weight(n):
    count = 0

    while n:
        n &= n - 1
        count += 1

    return count

Complexity. O(k) time and O(1) space, where k is the number of set bits. For a fixed 32-bit integer this is O(1), but the identity is useful beyond fixed widths.

LeetCode 338Easy

Bits
DP

Counting Bits

For every integer from 0 through n, return the number of 1 bits in its binary representation.

Approach. Use the count for a smaller number. Shifting right drops the lowest bit, so i >> 1 is i without its last bit. The answer for i is the answer for i >> 1, plus 1 if the dropped bit was set.

Show solution

def count_bits(n):
    bits = [0] * (n + 1)

    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)

    return bits

Complexity. O(n) time and O(n) space. Each value is computed once from a previous value already in the array.

The readability pitfall

Use bits when the state is naturally binary and compact: parity, masks, flags, small subsets. If the problem is about arbitrary values or ordered relationships, a hash set, sort, heap, or DP table will usually say the idea more plainly.