題目： LeetCode - 476. Number Complement

題目說明

給一個數字，求這個數字的補數。補數的取法就是將數字轉為二進制，然後對代表數字的部分做 not 運算。例如：

1
2
3
4
5： 00 00000 00000 00000 00000 00000 00|101
                                        ^ 從這裡開始
2： 00 00000 00000 00000 00000 00000 00|010
所以 5 的補數就是 2。

解題思路

先找出他代表數字的地方有幾位，求法就是一直往右推直到整個數字為 0。然後將數字往左推 count 位數，再使用 ~ 運算符對數字做 not 運算，最後再把 0 給推回去即可。
※ 關於 << 及 >> 運算符的介紹可參考本篇文章：LeetCode - 201 解題紀錄

參考解法

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findComplement(int num) {
        int count = 32, temp = num;
        while(temp > 0)
            temp >>= 1, --count;
        return ~(num << count) >> count;
    }
};