Portfolio/Learn/Bit Manipulation: Tricks Every Engineer Should Know
Algorithms & DSAdvanced

Bit Manipulation: Tricks Every Engineer Should Know

Learn the essential bit operations — XOR tricks, bit counting, power-of-two checks, bitmask DP, and how computers represent numbers at the lowest level.

12 min read
March 4, 2026
Bit ManipulationXORBitmaskBinaryPython

Essential Bit Operations

Bit manipulation operates on the binary representation of numbers. Key operations: AND (&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>). These run in O(1) and are the fastest operations a computer can perform. Many clever algorithms exploit bit properties for O(1) or O(n) solutions to seemingly complex problems.

python
# Fundamental bit tricks
def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

def count_set_bits(n: int) -> int:
    """Brian Kernighan's algorithm: O(number of set bits)."""
    count = 0
    while n:
        n &= n - 1  # Clear lowest set bit
        count += 1
    return count

def get_bit(n: int, i: int) -> bool:
    return bool(n & (1 << i))

def set_bit(n: int, i: int) -> int:
    return n | (1 << i)

def clear_bit(n: int, i: int) -> int:
    return n & ~(1 << i)

def toggle_bit(n: int, i: int) -> int:
    return n ^ (1 << i)

XOR Tricks

XOR has three magical properties: x ^ x = 0 (self-inverse), x ^ 0 = x (identity), and it's associative/commutative. This means XOR-ing all elements cancels out pairs, leaving the unique element.

python
def single_number(nums: list[int]) -> int:
    """Find the element that appears once (all others appear twice)."""
    result = 0
    for num in nums:
        result ^= num
    return result


def missing_number(nums: list[int]) -> int:
    """Find missing number in [0, n]. Uses XOR with indices."""
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

n & (n - 1) clears the lowest set bit. This is the basis for checking powers of two, counting bits, and many other tricks. Memorize this operation — it appears constantly.

Bitmask DP

When a problem involves choosing from a small set (typically n ≤ 20), represent the chosen subset as a bitmask. Each bit indicates whether an element is included. This enables DP over subsets in O(2^n * n) time.

python
def can_partition_k_equal_subsets(nums: list[int], k: int) -> int:
    """Check if array can be split into k subsets with equal sum."""
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort(reverse=True)

    # dp[mask] = remaining sum needed in current bucket
    dp = {0: 0}

    for mask in range(1 << n):
        if mask not in dp:
            continue
        for i in range(n):
            if mask & (1 << i):
                continue  # Already used
            new_mask = mask | (1 << i)
            if new_mask in dp:
                continue
            bucket_sum = dp[mask] % target
            if bucket_sum + nums[i] <= target:
                dp[new_mask] = dp[mask] + nums[i]

    return (1 << n) - 1 in dp

Bitmask DP is the go-to approach for problems like Traveling Salesman (small n), task assignment, partition into equal subsets, and any 'try all subsets' problem where n ≤ 20.

More Articles