Coding Interview PatternsNumber Complement
EasyBitwise Manipulation
Number Complement
Explanation & Solution
Description
The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.
- For example, the integer
5is101in binary and its complement is010which is the integer2.
Given an integer num, return its complement.
Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zeroes). The complement is 010, which is 2 in decimal.
Constraints
1 <= num < 2^31
Approach
Bitwise Manipulation pattern
Key Insight: Bit Mask
- To flip only the bits in
num's binary representation (without affecting leading zeros), we need a mask of the same length mask - 1gives us all 1s across the same number of bits asnum- XORing with all 1s flips every bit:
1 XOR 1 = 0,0 XOR 1 = 1
Algorithm
1. Find mask = the smallest power of 2 greater than num (by left-shifting until mask > num)
2. mask - 1 creates a bitmask of all 1s covering all bits in num
3. Return num ^ (mask - 1) to flip all bits in num
Example: num = 5 (binary 101)
- mask starts at 1, shifts:
1 → 2 → 4 → 8(8 > 5, stop) mask - 1 = 7 = 111in binary5 ^ 7 = 101 ^ 111 = 010 = 2✓
Key Insight
- Using
mask - 1ensures we only flip the meaningful bits, not all 32 bits - Time: O(log num) | Space: O(1)