Number Complement
Easy · Bit Manipulation · Bit Manipulation
Problem
Write the positive integer num in binary without leading zeros, flip every one of those bits (0 becomes 1, 1 becomes 0), and return the integer the flipped bits represent.
Only the bits up to and including the highest set bit of num are flipped; the endless run of leading zeros in front of it is left alone.
Examples
Input: num = 10 Output: 5
10 is 1010 in binary; flipping every digit gives 0101, which is 5.
Input: num = 7 Output: 0
7 is 111, so every digit becomes 0 and the answer is 0.
Input: num = 1 Output: 0
1 is a single digit 1; flipped, it is 0.
Constraints
- 1 <= num < 2^31
Approaches
- Baseline: digit by digit — time O(log num), space O(1)
Follow-up
The mask trick (all ones below the highest set bit) also gives the next power of two and the bit length. The use cases ask for the complement when 0 is allowed (one digit, so 0 becomes 1) and for the number of bit flips that turn one integer into another.
Related problems
Start free on Cariara · Coding problems · System design studio
