leetcode 476. Number Complement

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

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Input: 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: 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.

解法1:

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        # 0 => 1
        # 1 => 0
        # 2 => 0x10 => 0x01 => 1
        # 3 => 0x11 => 0x00 => 0
        # 4 => 0x100 => 0x011 => 3
        # 5 => 0x101 => 0x010 => 2
        # 6 = > 0x110 => 0x001 => 1
        # 7 => 0x111 => 0x000=>0
        # count the neareat 2^n of num, i.e. x
        # ans = x - num
        # calc x: move bit     
        if num == 0:
            return 1
        bits = 0
        n = num
        while n:
            bits += 1
            n = n>>1
        x = (1<<bits)-1
        return x-num

观察下就知道规律。

100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num, then do substraction

更精简一点的解法：

class Solution {
public:
    int findComplement(int num) {
        unsigned mask = ~0;
        while (num & mask) mask <<= 1;
        return ~mask & ~num;
    }
};

For example,

num          = 00000101
mask         = 11111000
~mask & ~num = 00000010

解法2:

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        # reverse every bit in num and constrcut answer
        if num == 0:
            return 1
        ans = 0
        n = num
        nth_bit = 0
        while n:
            if n & 1 == 0:
                ans += (1<<nth_bit)
            n = n>>1
            nth_bit += 1
        return ans

解法3:

 没有弄明白，后续再说。

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

mask |= mask >> 1will set the first left two bits to be 1, mask |= mask >> 2will set the first left four bits to be 1,
mask |= mask >> 4will set the first left 8 bits to be 1, … , at last, all the bits will be 1.