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

01. Find the Difference

Optimal Target: O(n) time · O(1) space

Given two lowercase English strings s and t, string t is formed by randomly shuffling all characters of s and inserting one extra character at an arbitrary index. Return the extra character added to t.

EXAMPLE 1
Input: s = "ab", t = "aeb"
Output: "e"
Explanation: XOR-ing the ASCII codes across "ab" and "aeb" cancels the matching 'a' pair and 'b' pair to 0, leaving ord('e'), which converts back to "e".
EXAMPLE 2
Input: s = "", t = "y"
Output: "y"
Explanation: With s empty, 0 ^ ord('y') evaluates directly to ord('y'), returning "y".
VISUAL INPUT
s then t
abaeb
running XOR
00000000
AUTOMATED TEST SUITE
Test Case 1
Input: "ab", "aeb"
Expected: "e"
Test Case 2
Input: "", "y"
Expected: "y"
Test Case 3
Input: "abcd", "abcde"
Expected: "e"
Pattern Trigger Hint ("How to Spot It")

all twins but one → XOR everything

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute find_the_difference against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

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