leetcode 476. Number Complement [Medium]

題目敘述

對一個整數的有效位元做位元補數（ones’ complement），例如 5 = 101，補數結果為 2 = 010，前面未使用到的 bit 不做任何操作。

思路

這題算是 Bit Manipulation 的入門題目，很適合練習 bit 的思考方式。這類題目之前做得不多，趁機記錄一下。

題目限制 1 <= num < 2^31，所以可確保最高位（第 31 bit）一定為 0：

找第一個有效位元

從最高位開始往右找，找到第一個 1 之後，後面所有的 bit 都是有效位數，再逐一反轉即可。

判斷某個位元是否為 1 的寫法：

if ((num & (1 << 31)) == 1) {
	// do something
}

找到第一個有效位元後，對後面所有的 bit 做反轉。

反轉 bits

• 方法一：逐個 bit 反轉，使用 XOR

class Solution {
public:
    int findComplement(int num) {
        bool flag = false;
        for (int shift = 31; shift >= 0; shift--) {
            if ((num & (1 << shift)) != 0) flag = true; 
            if (flag)
                num ^= (1 << shift);       
        }
        return num;
    }
};

• 方法二：找到第一個有效位元之後，一次性對後面所有 bits 做反轉（用 ~num 搭配 mask）

class Solution {
public:
    int findComplement(int num) {
        for (int shift = 31; shift >= 0; shift--) {
            if ((num & (1 << shift)) == 0) continue; 
            return ~num & ((1 << shift) - 1);
        }
        return num;
    }
};