Bit Manipulation

Overview

Bit manipulation operates directly on the binary representation of integers using AND, OR, XOR, NOT, and shifts. It enables compact state (bitmasks), constant-time set operations, and clever O(1) tricks that avoid arithmetic. Because each operation touches a fixed-width word, these techniques are typically O(1) per value and O(1) extra space.

Syntax / Usage

Combine masks and shifts to test, set, or clear a specific bit. The idioms below form the vocabulary for most bit-level algorithms.

def get_bit(x, i):    return (x >> i) & 1          # read bit i
def set_bit(x, i):    return x | (1 << i)          # turn bit i on
def clear_bit(x, i):  return x & ~(1 << i)         # turn bit i off
def toggle_bit(x, i): return x ^ (1 << i)          # flip bit i

def is_power_of_two(x):                             # O(1) time and space
    return x > 0 and (x & (x - 1)) == 0            # clears lowest set bit

Examples

XOR finds the single unpaired number because a ^ a == 0 and XOR is commutative:

def single_number(nums):              # O(n) time, O(1) space
    result = 0
    for n in nums:
        result ^= n
    return result

print(single_number([4, 1, 2, 1, 2]))  # 4

Count set bits by repeatedly clearing the lowest set bit (Brian Kernighan's trick):

def count_bits(x):                    # O(number of set bits) time
    count = 0
    while x:
        x &= x - 1                    # drops the lowest 1 bit each step
        count += 1
    return count

print(count_bits(0b1011))  # 3

Common Mistakes

• Confusing logical operators (and, or) with bitwise operators (&, |).
• Forgetting operator precedence, so x & 1 == 0 parses as x & (1 == 0); add parentheses.
• Assuming fixed-width behavior in Python, where integers are arbitrary precision and never overflow.
• Shifting by a negative or oversized amount, which raises or produces unexpected results.
• Mishandling signed numbers; Python's ~x equals -x - 1, not a plain bit flip in a fixed width.

See Also

algorithms-big-o-notation algorithms-dynamic-programming algorithms-divide-and-conquer