Bit Manipulation Pattern: LeetCode Guide & Problems

Use bitwise operations to solve XOR, subset, and number theory problems.

✓ Pattern Solutions & Guides Practice Mode Enabled

8 Problem 6 Easy 2 Medium 0 Hard

Overview

Bit manipulation uses bitwise AND, OR, XOR, NOT, and shifts for highly efficient solutions. XOR is particularly powerful: x ^ x = 0 and x ^ 0 = x.

When to Use

Single number (XOR trick)
Number of 1 bits (Hamming weight)
Counting bits
Reverse bits
Missing number
Sum of two integers without +

Common Mistakes

Signed vs unsigned right shift (>>> vs >>)
Operator precedence — always use parentheses
Not knowing n & (n-1) clears the lowest set bit

Complexity

Time

O(1) or O(log n) for most operations

Space

O(1)

// Common bit tricks
int getBit(int n, int i) { return (n >> i) & 1; }
int setBit(int n, int i) { return n | (1 << i); }
int clearBit(int n, int i) { return n & ~(1 << i); }
boolean isPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }
int lowestSetBit(int n) { return n & (-n); }
int clearLowestBit(int n) { return n & (n - 1); }

// XOR: find single number where all others appear twice
public int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

Problems (8)

Hide completed

Problem	Difficulty	Companies	Freq	Solution
Single Number #Array #Bit Manipulation	Easy	AmazonApple +1	High	Solution
Missing Number #Array #Math #Bit Manipulation	Easy	MicrosoftAmazon	High	Solution
Counting Bits #DP #Bit Manipulation	Easy	GoogleFacebook	High	Solution
Number of 1 Bits #Divide and Conquer #Bit Manipulation	Easy	AppleMicrosoft +1	High	Solution
Reverse Bits #Divide and Conquer #Bit Manipulation	Easy	AppleAmazon	Medium	Solution
Sum of Two Integers #Math #Bit Manipulation	Medium	FacebookAmazon +1	Medium	Solution
Single Number II #Array #Bit Manipulation	Medium	AmazonFacebook	Medium	Solution
Power of Two #Math #Bit Manipulation #Recursion	Easy	GoogleApple	Medium	Solution

🧠

Mastering the Bit Manipulation Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Bit Manipulation pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Bit Manipulation, the target time complexity is typically O(1) or O(log n) for most operations while maintaining an auxiliary space complexity of O(1). Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.