476. Number Complement的C++解法

    xiaoxiao2021-03-25  24

    本来以为上一道题我的写法是最蠢的,没想到这道题用了更蠢的写法,而且竟然没想出来怎么写效率更高。运行速度垫底。

    class Solution { public: int findComplement(int num) { int x[32]; int i = 31; while (num) { x[i] = num % 2; num = num / 2; i = i - 1; } int k = i; int sum = 0; int l = 1; for (i = 31; i > k; i--) { if (x[i] == 0) sum = sum + l; l = l * 2; } return sum; } };

    最优解思路:

    仍然是按位操作取反即可,但是要想办法把前面的0过滤掉。使用掩码mask与原数做&运算找到前面所有多出来的0,将mask取反再与原数做&即可只保留不为0的部分。

    最优解代码:

    class Solution { public: int findComplement(int num) { unsigned mask = ~0; while (num & mask) mask <<= 1; return ~mask & ~num; } }; ~:按位取反,0在内存中的存储方式是所有位为0,即00000000。按位取反后为11111111(在机器中表示-1)。

    转载请注明原文地址: https://ju.6miu.com/read-50158.html

    最新回复(0)