476. Number Complement

Problem 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 5 is 101 in binary and its complement is 010 which is the integer 2.

Given an integer num, return its complement.

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:

• 1 <= num < 2³¹

Python Solution

class Solution:
    def findComplement(self, num: int) -> int:
        # Find the number of bits in num
        if num == 0:
            return 1
            
        # Calculate mask with all 1's up to the highest bit of num
        mask = num
        mask |= mask >> 1
        mask |= mask >> 2
        mask |= mask >> 4
        mask |= mask >> 8
        mask |= mask >> 16
        
        # XOR with mask to flip all bits
        return num ^ mask

Java Solution

class Solution {
    public int findComplement(int num) {
        // Find the number of bits in num
        if (num == 0) {
            return 1;
        }
        
        // Calculate mask with all 1's up to the highest bit of num
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        
        // XOR with mask to flip all bits
        return num ^ mask;
    }
}

C++ Solution

class Solution {
public:
    int findComplement(int num) {
        // Find the number of bits in num
        if (num == 0) {
            return 1;
        }
        
        // Calculate mask with all 1's up to the highest bit of num
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        
        // XOR with mask to flip all bits
        return num ^ mask;
    }
};

JavaScript Solution

/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    // Find the number of bits in num
    if (num === 0) {
        return 1;
    }
    
    // Calculate mask with all 1's up to the highest bit of num
    let mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    
    // XOR with mask to flip all bits
    return num ^ mask;
};

C# Solution

public class Solution {
    public int FindComplement(int num) {
        // Find the number of bits in num
        if (num == 0) {
            return 1;
        }
        
        // Calculate mask with all 1's up to the highest bit of num
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        
        // XOR with mask to flip all bits
        return num ^ mask;
    }
}