Essential Bit Manipulation Tricks and Optimization Techniques from the LeetCode Repository

Bit manipulation tricks like XOR cancellation, low-bit extraction, and subset masking enable O(1) space solutions for complex problems by operating directly on binary representations.

The azl397985856/leetcode repository contains a comprehensive collection of bit manipulation techniques documented in thinkings/bit.md and applied across numerous problem solutions. These bit manipulation tricks transform memory-intensive algorithms into constant-space solutions by exploiting properties of binary arithmetic, from isolating specific bits to encoding entire state spaces within a single integer.

XOR Cancellation for Duplicate Removal

The XOR operation provides a constant-space method to identify elements with odd frequencies. Because a ^ a = 0 and a ^ 0 = a, XORing all elements in an array cancels out pairs of identical numbers, leaving only the unique value.

This technique appears in thinkings/bit.md (lines 23-35) and powers solutions for LeetCode 136, 137, and 260. The implementation requires a single pass through the array:

# From thinkings/bit.md (lines 29-35)

def single_number(nums):
    res = 0
    for n in nums:
        res ^= n          # XOR cancels pairs

    return res

Low-Bit Extraction and Bit Clearing

Two fundamental operations enable efficient bit traversal: isolating the rightmost set bit and clearing it.

Low-Bit Extraction with x & -x

Low-bit extraction uses the two's complement property where -x = ~x + 1. The expression x & -x isolates the least significant 1-bit. This appears in the N-Queens II solution in problems/52.N-Queens-II.md (lines 79-84), where it extracts valid queen positions:

// From problems/52.N-Queens-II.md (lines 79-84)
const p = bits & -bits;      // isolate lowest 1-bit
bits &= bits - 1;            // clear that bit

Clearing Bits with x &= x - 1

Clearing the low-bit via x &= x - 1 removes the rightmost set bit. This Brian Kernighan algorithm counts set bits in O(number of 1-bits) time, documented in thinkings/bit.md (lines 49-50) and used in problem 191:

def count_bits(x):
    cnt = 0
    while x:
        x &= x - 1   # clear lowest set bit

        cnt += 1
    return cnt

Bitmasking for State Compression

Bitmasking encodes set membership into integers where each bit represents presence or absence of an element. This technique reduces space complexity from O(N) to O(1) for small universes (typically N ≤ 32).

In the N-Queens II solution (problems/52.N-Queens-II.md), three bitmasks track occupied columns and diagonals:

// Bitmask DFS for N-Queens
let bits = (~(cols | pie | na)) & ((1 << n) - 1); // available positions

The expression (1 << n) - 1 generates a mask of n low bits, documented in thinkings/bit.md (lines 51-52). This width-limiting mask simulates fixed-width arithmetic in languages with arbitrary-precision integers.

Simulated Arithmetic Without Operators

Bit manipulation can implement addition without the + operator by handling sum and carry separately. The XOR operation computes the sum without carry, while AND followed by left-shift computes the carry bits.

This algorithm appears in problems/371.sum-of-two-integers.md (lines 36-41):

// From problems/371.sum-of-two-integers.md (lines 36-41)
function getSum(a, b) {
    while (b !== 0) {
        const carry = (a & b) << 1; // compute carry
        a = a ^ b;                  // sum without carry
        b = carry;
    }
    return a;
}

For 32-bit signed integers, the implementation requires masking with 0xFFFFFFFF to handle overflow and sign extension correctly, as noted in the repository's Python implementations.

Subset Enumeration with Bit Manipulation

Enumerating all subsets of a bitmask efficiently uses the trick sub = (sub - 1) & mask. This iterates through all non-empty subsets without recursion, running in O(2^k) time for a mask with k bits.

This technique powers the solution for LeetCode 1178 (Number of Valid Words for Each Puzzle) in problems/1178.number-of-valid-words-for-each-puzzle.md (lines 132-146):

# Subset enumeration pattern from problems/1178...

sub = mask
while True:
    # process subset sub

    total += cnt.get(sub | first, 0)
    if sub == 0: 
        break
    sub = (sub - 1) & mask   # key: iterate to next subset

The repository also uses this pattern for checking word subsets against puzzle constraints, where each word and puzzle is encoded as a 26-bit mask representing letter presence.

Summary

• XOR cancellation eliminates duplicate pairs in O(N) time with O(1) space, implemented in thinkings/bit.md and problem 136 solutions.
• Low-bit extraction (x & -x) and bit clearing (x &= x-1) provide O(1) operations for isolating and removing specific bits, critical for N-Queens and bit counting.
• Bitmask state compression encodes complex states into single integers, reducing space complexity for problems like N-Queens II as shown in problems/52.N-Queens-II.md.
• Simulated arithmetic using XOR and AND operations implements addition without standard operators, documented in problems/371.sum-of-two-integers.md.
• Subset enumeration via (sub-1) & mask efficiently iterates through all subsets in O(2^k) time, applied in problems/1178.number-of-valid-words-for-each-puzzle.md.

Frequently Asked Questions

What is the XOR trick for finding a single number in an array?

The XOR trick exploits the properties that a ^ a = 0 and a ^ 0 = a. By XORing all elements in the array, pairs of identical numbers cancel out to zero, leaving only the element that appears an odd number of times. This approach runs in O(N) time with O(1) space, as implemented in thinkings/bit.md and the solution for LeetCode 136.

How does the low-bit extraction technique work in the N-Queens problem?

Low-bit extraction uses the expression x & -x to isolate the rightmost set bit in a bitmask. In the N-Queens II solution (problems/52.N-Queens-II.md), this technique extracts valid queen positions from a bitmask representing available columns and diagonals. The operation works because two's complement negation flips all bits and adds one, causing all bits except the lowest set bit to become zero when ANDed with the original value.

What is the Brian Kernighan bit counting algorithm?

The Brian Kernighan algorithm counts set bits by repeatedly clearing the lowest set bit using x &= x - 1. Each iteration removes exactly one 1-bit, so the loop runs in O(number of set bits) time rather than O(bit width). This technique is documented in thinkings/bit.md (lines 49-50) and applied in solutions for LeetCode 191 (Number of 1 Bits), offering superior performance when integers contain few set bits.

How can bit manipulation simulate addition without using the plus operator?

Bit manipulation simulates addition by separating the sum and carry operations. The XOR operation (a ^ b) calculates the sum without considering carry bits, while the AND operation followed by a left shift ((a & b) << 1) computes the carry bits. By repeating this process until the carry becomes zero, the algorithm produces the correct sum. This approach is implemented in problems/371.sum-of-two-integers.md (lines 36-41) and requires 32-bit masking in languages like Python to handle overflow correctly.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}