Dashboard/Coding patterns/27. Bitwise Manipulation

CODING PATTERNS · LESSON 27 OF 28 · 53 MIN VIDEO · 18 PROBLEMS

Bitwise Manipulation

Module Progress (0 / 18 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (53 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

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.

WHEN TO USE THIS PATTERN
  • 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.
COMMON INTERVIEW PITFALLS
  • 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)) == 0 and (v & k) == 0.
  • Zero and negative inputs in single-bit and mask loops: 0 & (0 - 1) evaluates to 0, so power-of-two checks require n > 0; similarly, mask-growing loops (while mask < n:) must initialize mask = 1 so n = 0 still receives a 1-bit mask.
  • Stopping early during fixed-width bit reversal: Using while n: instead of for _ in range(32): drops leading zero MSBs in n and leaves previously shifted bits stranded in low-order positions.
Prefix Parity Bitmask & Earliest-Index LookupFinding the longest substring or subarray in which tracked items appear an even number of times (prefix XOR collision).
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 best
Per-Column Bit Counting Modulo kIsolating a single outlier in O(1) space when all other 32-bit signed integers appear exactly k times.
def 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 res
Kernighan's Lowest-Set-Bit ClearingCounting set 1-bits in O(popcount(n)) steps or testing whether an integer is a power of two.
def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count
🔒 PRO PROBLEMTarget: O(1) time · O(1) space

17. Minimum Operations to Make the Integer Zero

Pattern Trigger: sum of powers of two → count the 1 bits

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

What's seven X-OR two X-OR seven?