476. Number Complement

Difficulty: Easy

Related Topics: Bit Manipulation

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

Example 1:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010\. So you need to output 2.

Example 2:

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0\. So you need to output 0.

Constraints:

• The given integer num is guaranteed to fit within the range of a 32-bit signed integer.
• num >= 1
• You could assume no leading zero bit in the integer’s binary representation.
• This question is the same as 1009:

Solution

Language: Java

class Solution {

    public int findComplement(int num) {
        // count the bit length
        // e.g. 
        // 5  (101) return 3
        // 10 (1010) return 4
        int n = bitLen(num);

        // flip each bit
        //
        // xor
        // -------
        // 0 0 | 0 
        // 0 1 | 1   <-
        // 1 0 | 1
        // 1 1 | 0   <-
        // -------
        //
        // 0 ^ 1 = 1
        // 1 ^ 1 = 0
        //
        for (int i = 0; i < n; i++) {
            // where i is the bit that is to be flip
            num ^= 1 << i;
        }

        return num;
    }

    private int bitLen(int a) {
        return 32 - Integer.numberOfLeadingZeros(a);
    }
}