number-complement

Number Complement – LeetCode 476

Problem

Description

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

Note:

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

Answer

Original

Code

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

思路

通过构造mask来去掉不需要的反转部分。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$5$ ms，排名$76.79\%$

Better

思路

通过二分法构造造mask来去掉不需要的反转部分。时间复杂度$O(log{n})$，空间复杂度$O(1)$。
耗时$5$ ms，排名$76.79\%$

Code

class Solution {
public:
    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;
    }
};