Bitwise Manipulation — How the Pattern Works
Bitwise manipulation operates directly on the binary representation of integers using word-parallel logical and shift operators (&, |, ^, ~, <<, >>), processing 32 or 64 independent bit columns in O(1) CPU instructions. Its core invariants leverage self-inverse XOR cancellation (x ^ x == 0 and x ^ 0 == x), compact state compression via k-bit integer masks, independent modulo-k column counting, and lowest-set-bit clearing via n & (n - 1). Replacing hash sets, explicit subset enumeration, and multi-pass subarray scans with bit-level invariants routinely reduces O(2^n) and O(n^2) brute-force solutions to O(n) time and O(1) auxiliary space.
- Every element repeats k times (commonly k = 2 or k = 3) except a single outlier, with a strict O(n) time and O(1) auxiliary space constraint.
- Subarray or substring validity depends only on odd/even element counts (parity) or range XOR equality (prefix[r] ^ prefix[l] == 0).
- A small universe of k <= 20 boolean flags, character parities, or binary digit choices can be packed into an integer bitmask or binary index.
- Aggregating bitwise XOR, AND, or OR across all subsets, subarrays, or k-tuples where independent bit-column linearity or monotonic bit loss/gain applies.
- Direct binary structure queries on integers, such as power-of-two checks, Hamming weight/distance, fixed-width bit reversal, Gray code distance, or power-of-two decompositions.
- Arbitrary-precision signed integers in Python: Python ints have unbounded leading sign bits (~10 evaluates to -11, and 1 << 31 evaluates to +2147483648). Always bound inversions with an explicit width mask (n ^ mask) and convert reconstructed 32-bit two's complement values via
if res >= (1 << 31): res -= (1 << 32). - Operator precedence traps: Arithmetic (+, -) and comparison (==, !=) operators have subtle precedence interactions with &, ^, and | across languages. Always parenthesize bitwise subexpressions explicitly, such as
(n & (n - 1)) == 0and(v & k) == 0. - Zero and negative inputs in single-bit and mask loops:
0 & (0 - 1)evaluates to 0, so power-of-two checks requiren > 0; similarly, mask-growing loops (while mask < n:) must initializemask = 1son = 0still receives a 1-bit mask. - Stopping early during fixed-width bit reversal: Using
while n:instead offor _ in range(32):drops leading zero MSBs innand leaves previously shifted bits stranded in low-order positions.
def longest_even_parity_span(items, bit_index):
first_seen = {0: -1}
mask = best = 0
for i, x in enumerate(items):
b = bit_index(x)
if b >= 0:
mask ^= 1 << b
if mask in first_seen:
best = max(best, i - first_seen[mask])
else:
first_seen[mask] = i
return bestdef single_number_mod_k(nums, k=3):
res = 0
for bit in range(32):
col_sum = sum((v >> bit) & 1 for v in nums)
if col_sum % k:
res |= 1 << bit
if res >= 1 << 31:
res -= 1 << 32
return resdef count_set_bits(n):
count = 0
while n:
n &= n - 1
count += 1
return count