NeetCode 150 · Bit Manipulation

Bit Manipulation Problems

XOR for toggle/cancel, AND for masking, shifts for multiply/divide by 2. Bit tricks are elegant but require knowing specific properties of binary operations.

Problems: 7
Easy: 5
Medium: 2
Hard: 0
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Easy ArrayBit Manipulation
Every element appears twice except one. Find that single element. Must use O(1) extra space.
Test Cases
singleNumber([2,2,1]) → 1 singleNumber([4,1,2,1,2]) → 4 singleNumber([1]) → 1
XORa^a=0a^0=a
XOR all numbers. Pairs cancel out (a^a=0). What's left is the single number.
Python Solution
def singleNumber(nums): result = 0 for n in nums: result ^= n # pairs cancel, single remains return result
Key idea: XOR has two key properties: a ^ a = 0 (same number cancels) and a ^ 0 = a (identity). XOR-ing all numbers cancels all pairs, leaving only the unique element.
Time: O(n).
Space: O(1).
02 Easy Divide and ConquerBit Manipulation
Return the number of '1' bits in a given 32-bit unsigned integer (Hamming weight).
Test Cases
hammingWeight(11) → 3 # 0b1011 hammingWeight(128) → 1 # 0b10000000 hammingWeight(2147483645) → 30
n & (n-1) clears LSBO(k) k=set bitsBrian Kernighan
The trick n & (n-1) clears the lowest set bit. Count how many times you can do this before n becomes 0.
Python Solution
def hammingWeight(n): count = 0 while n: n &= n - 1 # clear the lowest set bit count += 1 return count
Key idea: Brian Kernighan's trick: n & (n-1) always clears the rightmost set bit. Count iterations until n becomes 0. This runs in O(k) where k is the number of set bits.
Time: O(k) where k = number of 1-bits.
Space: O(1).
03 Easy DPBit Manipulation
Given integer n, return array ans of length n+1 where ans[i] is the number of 1's in binary representation of i.
Test Cases
countBits(2) → [0,1,1] countBits(5) → [0,1,1,2,1,2]
dp[i] = dp[i>>1] + (i&1)right shift trickO(n)
dp[i] = dp[i >> 1] + (i & 1). Shifting right drops the last bit; the popcount is the same except possibly for that last bit.
Python Solution
def countBits(n): dp = [0] * (n + 1) for i in range(1, n + 1): dp[i] = dp[i >> 1] + (i & 1) return dp
Key idea: dp[i] = dp[i // 2] + (i % 2). Shifting right drops the LSB. The number of 1-bits is the parent's count plus 1 if the LSB was set.
Time: O(n).
Space: O(n).
04 Easy Divide and ConquerBit Manipulation
Reverse bits of a given 32-bit unsigned integer.
Test Cases
reverseBits(43261596) → 964176192 # 0b00000010100101000001111010011100 # → 0b00111001011110000010100101000000
shift and OR 32 timesO(32)=O(1)
Build the result bit by bit. Extract the LSB of n, shift it to the appropriate position in result, and move to the next bit.
Python Solution
def reverseBits(n): result = 0 for _ in range(32): result = (result << 1) | (n & 1) # shift result left, add LSB of n n >>= 1 return result
Key idea: Iterate 32 times. Each iteration: shift result left by 1, OR in the LSB of n, then shift n right. This builds the reversed 32-bit number.
Time: O(1) — always 32 iterations.
Space: O(1).
05 Easy ArrayMathBit Manipulation
Given n distinct numbers in range [0,n], find the missing number.
Test Cases
missingNumber([3,0,1]) → 2 missingNumber([0,1]) → 2 missingNumber([9,6,4,2,3,5,7,0,1]) → 8
Gauss sum formulaor XOR approachO(n) O(1)
Expected sum = n*(n+1)/2. Actual sum = sum(nums). Missing = expected - actual.
Python Solution
def missingNumber(nums): n = len(nums) return n * (n + 1) // 2 - sum(nums)
Key idea: The sum of 0..n is n*(n+1)/2. The missing number is the difference between expected and actual sums. Clean O(1) math solution.
Time: O(n).
Space: O(1).
06 Medium MathBit Manipulation
Calculate the sum of two integers without using + or - operators.
Test Cases
getSum(1, 2) → 3 getSum(-1, 1) → 0 getSum(2, 3) → 5
XOR for sum bitsAND<<1 for carry32-bit mask
XOR gives sum bits (without carry). AND gives carry bits — shift them left by 1. Repeat until carry is zero. Use a 32-bit mask for Python.
Python Solution
def getSum(a, b): mask = 0xFFFFFFFF while b & mask: a, b = (a ^ b) & mask, ((a & b) << 1) & mask # Convert from 32-bit unsigned to Python signed int if a > 0x7FFFFFFF: a = ~(a ^ mask) return a
Key idea: a ^ b gives the sum bits without carry. (a & b) << 1 gives the carry bits. Repeat until no carry. The mask handles Python's arbitrary precision int by constraining to 32 bits.
Time: O(1) — at most 32 iterations.
Space: O(1).
07 Medium Math
Given signed 32-bit integer, reverse its digits. Return 0 if result overflows 32-bit signed integer range.
Test Cases
reverse(123) → 321 reverse(-123) → -321 reverse(120) → 21 reverse(1534236469) → 0 # overflow
str reversal32-bit overflow checksign handling
Convert to string for easy reversal. Handle sign separately. Check if result is in [-2³¹, 2³¹-1].
Python Solution
def reverse(x): sign = -1 if x < 0 else 1 x = abs(x) rev = int(str(x)[::-1]) # reverse digits rev *= sign if rev < -(2**31) or rev > 2**31 - 1: return 0 # overflow return rev
Key idea: Separate sign from digits, reverse the digit string, restore the sign, then check for 32-bit overflow. Simple and clean.
Time: O(log x) — number of digits.
Space: O(log x).
← Prev Category