What is the Bit Manipulation pattern?

The Bit Manipulation pattern is a systematic approach to solving a class of coding interview problems. By recognizing the Bit Manipulation structure, you can solve problems in optimal time complexity using proven techniques.

When should I use the Bit Manipulation pattern?

Use the Bit Manipulation pattern when the problem structure matches its recognition signals — typically when brute force would be O(n²) or worse, and the pattern reduces complexity to O(1) per bit op.

What is the time complexity of Bit Manipulation?

The Bit Manipulation pattern typically runs in O(1) per bit op time and uses O(1) space. The exact complexity depends on the specific sub-variant being applied.

Is Bit Manipulation important for coding interviews?

Yes — the Bit Manipulation pattern is frequently tested at FAANG companies and competitive engineering interviews. Mastering this pattern gives you a reliable framework to solve many problem variations quickly.

How do I practice the Bit Manipulation pattern?

Start by studying the pattern's mental model and recognition signals on DSAPatterns, then practice the curated LeetCode problems below in order from Easy to Hard. Aim for pattern recognition before memorizing solutions.

← back to patterns

pattern / MEDIUM

Bit Manipulation.

Operate on binary representations

complexity

time

O(1) per bit op

space

O(1)

practice questions

browse and solve all 7 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Use XOR for finding unique, AND for masking, OR for setting bits, shift for multiplication/division by 2.

Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) to solve problems efficiently.

when to use ✓

01Single number (XOR)
02Counting bits
03Power of two
04Subsets via bitmask

when not ✗

01When arithmetic operations are clearer

04'

recognition signals

Single number problems

Subset generation

Power of two

Bit counting

XOR tricksBit maskingBit countingBitmask DP

05'

templates

python

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3   n = len(nums)
4   if n < k:
5      return 0
6   window_sum = sum(nums[:k])
7   max_sum = window_sum
8   for i in range(k, n):
9      window_sum += nums[i] - nums[i - k]
10      max_sum = max(max_sum, window_sum)
11   return max_sum

common mistakes

01Sign extension in right shift
02Confusing & vs &&
03Integer overflow in shifts

interview tips

01Master: a^a=0, a^0=a, a&(-a) gives lowest set bit
02Practice bitmask DP for small N

06'

practice this pattern

7 curated problems from LeetCode

See all

Single Number# · Bit Manipulation

EASY

Number of 1 Bits# · Bit Manipulation

EASY

Counting Bits# · Bit Manipulation

EASY

Reverse Bits# · Bit Manipulation

EASY

Bitwise AND of Numbers Range# · Bit Manipulation

MEDIUM

Single Number III# · Bit Manipulation

MEDIUM

Sum of Two Integers# · Bit Manipulation

MEDIUM

07'

faq

← back to patterns

pattern / MEDIUM

Bit Manipulation.

Operate on binary representations

complexity

time

O(1) per bit op

space

O(1)

practice questions

browse and solve all 7 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Use XOR for finding unique, AND for masking, OR for setting bits, shift for multiplication/division by 2.

Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) to solve problems efficiently.

when to use ✓

01Single number (XOR)
02Counting bits
03Power of two
04Subsets via bitmask

when not ✗

01When arithmetic operations are clearer

04'

recognition signals

Single number problems

Subset generation

Power of two

Bit counting

XOR tricksBit maskingBit countingBitmask DP

05'

templates

python

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3   n = len(nums)
4   if n < k:
5      return 0
6   window_sum = sum(nums[:k])
7   max_sum = window_sum
8   for i in range(k, n):
9      window_sum += nums[i] - nums[i - k]
10      max_sum = max(max_sum, window_sum)
11   return max_sum