Solution Explanation for LeetCode 476: Number Complement

This problem asks us to find the bitwise complement of a given integer. The bitwise complement flips all the bits (0s become 1s, and 1s become 0s).

Approach 1: Bit Manipulation using XOR

This approach is efficient and concise. It leverages the XOR (exclusive OR) operator's property of flipping bits.

1. Find the number of bits: We need to determine how many bits are needed to represent the input number num. We can use num.bit_length() in Python or Integer.numberOfLeadingZeros() in Java (and similar functions in other languages) to efficiently find the number of bits needed.

2. Create a mask: We create a mask that consists of all 1s up to the number of bits required to represent num. This mask will have the same length as the binary representation of num. We achieve this using bit shifting (1 << num.bit_length()). Subtracting 1 from the result ensures that all bits in the mask are 1.

3. XOR operation: We perform a bitwise XOR operation between num and the mask. XOR flips the bits: 1 XOR 1 = 0, and 0 XOR 1 = 1. This directly yields the complement.

Time Complexity: O(log n), where n is the input number. This is because the bit length of a number is logarithmic with respect to its value. The bitwise operations themselves are considered constant time.

Space Complexity: O(1). We only use a few variables to store intermediate results.

Code Examples:

Python:

class Solution:
    def findComplement(self, num: int) -> int:
        return num ^ ((1 << num.bit_length()) - 1)

Java:

class Solution {
    public int findComplement(int num) {
        return num ^ ((1 << (32 - Integer.numberOfLeadingZeros(num))) - 1);
    }
}

C++:

class Solution {
public:
    int findComplement(int num) {
        return num ^ ((1LL << (64 - __builtin_clzll(num))) - 1);
    }
};

Go:

func findComplement(num int) int {
	return num ^ ((1 << bits.Len(uint(num))) - 1)
}

TypeScript/JavaScript:

function findComplement(num: number): number {
    return num ^ (2 ** num.toString(2).length - 1);
}
 
// JavaScript is identical

Approach 2: Bit Manipulation using Inversion and AND

This approach uses the bitwise NOT operator (~) to invert all bits and then performs a bitwise AND operation to ensure the result is within the correct number of bits.

1. Bitwise NOT: The ~ operator flips all bits. However, this operation considers the number to be a much larger integer (e.g., a 64-bit number in many systems), so it might result in leading 1s that need to be removed.

2. Bitwise AND: We use a mask created in a similar way as in Approach 1 to zero out any extraneous leading 1s created by the bitwise NOT operation.

Time Complexity: O(log n) due to the bit length calculation and bitwise operations.

Space Complexity: O(1)

Code Examples:

TypeScript/JavaScript:

function findComplement(num: number): number {
    return ~num & (2 ** num.toString(2).length - 1);
}

This approach is less readable than Approach 1 but achieves the same result with slightly different bitwise operations. Approach 1 is generally preferred for its clarity and efficiency.