Bit Manipulation Patterns in Java - Interview Preparation Guide

Bit manipulation is the interview pattern for compressing boolean state, exploiting binary structure, and replacing extra memory with constant-time bitwise operations. Strong candidates do not treat it as a bag of tricks. They explain what each bit represents, why the bitwise operation preserves the invariant, and where signed-integer edge cases matter in Java.

Pattern Summary Table

Problem Statement

Given integers, masks, or subset-style state, use binary representation to answer queries, compress flags, or derive values faster than counting or hashing would allow.

Pattern Recognition Signals

• Keywords in the problem: mask, XOR, parity, power of two, subset state, bit count.
• Structural signal: the problem becomes easier when each boolean decision or repeated pair-cancellation can be modeled directly in binary.
• Complexity signal: the optimized version avoids repeated rescans, recomputation, or state explosion that brute force would suffer.

Java Template

public int singleNumber(int[] nums) {
    int x = 0;
    for (int n : nums) x ^= n;
    return x;
}

Core Bit Operations (Quick Reference)

• check kth bit: (x & (1 << k)) != 0
• set kth bit: x |= (1 << k)
• clear kth bit: x &= ~(1 << k)
• toggle kth bit: x ^= (1 << k)
• remove lowest set bit: x &= (x - 1)

These are building blocks for most bit-manipulation problems.

Dry Run (Single Number via XOR)

Input: [4, 1, 2, 1, 2]

x=0
x^=4 -> 4
x^=1 -> 5
x^=2 -> 7
x^=1 -> 6
x^=2 -> 4

Pairs cancel because a ^ a = 0, leaving unique value 4.

Common Advanced Patterns

1. subset enumeration with bitmask loops
2. parity and power-of-two checks
3. counting set bits with n &= (n - 1)
4. two-unique-elements split by rightmost set bit

Power-of-two check:

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Signed Integer Caution in Java

Java int is signed 32-bit two’s complement. For unsigned right shift, use >>> (not >>).

int x = -8;
System.out.println(x >> 1);  // keeps sign bit
System.out.println(x >>> 1); // zero-fills from left

Use long where shifts or additions can overflow int.

Problem 1: Single Number

Problem description: Given an array where every value appears twice except one, return the element that appears only once.

What we are solving actually: A hash map works, but the hidden shortcut is that duplicate bits cancel under XOR, so we can compress the whole scan into one running variable.

What we are doing actually:

1. Start with x = 0.
2. XOR every number into x.
3. Let duplicate values cancel automatically.
4. Return the value left in x.

public int singleNumber(int[] nums) {
    int x = 0;
    for (int n : nums) {
        x ^= n; // Matching values cancel, so only the unique number survives.
    }
    return x;
}

Debug steps:

• print x after each XOR to watch duplicates cancel in sequence
• test [7] and [4,1,2,1,2] to cover singleton and normal input
• verify the invariant that x equals XOR of all values processed so far

Problem-Fit Checklist

• Identify whether input size or query count requires preprocessing or specialized data structures.
• Confirm problem constraints (sorted input, non-negative weights, DAG-only, immutable array, etc.).
• Validate that the pattern gives asymptotic improvement over brute-force under worst-case input.
• Define explicit success criteria: value only, index recovery, count, path reconstruction, or ordering.

Invariant and Reasoning

• Write one invariant that must stay true after every transition (loop step, recursion return, or update).
• Ensure each step makes measurable progress toward termination.
• Guard boundary states explicitly (empty input, singleton, duplicates, overflow, disconnected graph).
• Add a quick correctness check using a tiny hand-worked example before coding full solution.

Complexity and Design Notes

• Compute time complexity for both preprocessing and per-query/per-update operations.
• Track memory overhead and object allocations, not only Big-O notation.
• Prefer primitives and tight loops in hot paths to reduce GC pressure in Java.
• If multiple variants exist, choose the one with the simplest correctness proof first.

Production Perspective

• Convert algorithmic states into explicit metrics (queue size, active nodes, cache hit ratio, relaxation count).
• Add guardrails for pathological inputs to avoid latency spikes.
• Keep implementation deterministic where possible to simplify debugging and incident analysis.
• Separate pure algorithm logic from I/O and parsing so the core stays testable.

Implementation Workflow

1. Implement the minimal correct template with clear invariants.
2. Add edge-case tests before optimizing.
3. Measure complexity-sensitive operations on realistic input sizes.
4. Refactor for readability only after behavior is locked by tests.

Common Mistakes

1. Choosing the pattern without proving problem fit.
2. Ignoring edge cases (empty input, duplicates, overflow, disconnected state).
3. Mixing multiple strategies without clear invariants.
4. No complexity analysis against worst-case input.

Practice Set (Recommended Order)

1. Single Number (LC 136)
   LeetCode
2. Counting Bits (LC 338)
   LeetCode
3. Number of 1 Bits (LC 191)
   LeetCode

Key Takeaways

• This pattern is most effective when transitions are explicit and invariants are enforced at every step.
• Strong preconditions and boundary handling make these implementations production-safe.
• Reuse this template and adapt it per problem constraints.