leetcode 476. Number Complement [Medium]

davidlei included in leetcode

2021-12-27 151 words One minute

Contents

題目敘述

對一個整數的有效位元做位元轉換(ones' complement)，像是 5 = 101，經過轉換之後結果 2 = 010，前面沒有用到的 bit 則是不做任何操作。

思路

這題算是 Bit Manipulation 的入門題目，很適合練習 bit 的思考方式。剛好這類型的題目之前沒什麼做過，所以這邊來紀錄一下。

因為這題的範圍限制 1 <= num < 2^31，所以可確保第一個 bit 為0

找第一個有效位元

我的想法是先從左邊第一個 bit 開始找，找到第一個 1 ，後面所有的 bit 就都是有效位數，再一一反轉。

要判斷左邊第一個位元是不是 1 可以寫成

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

可以利用這個方式先找到第一個 1 的所在，在對於後面的 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

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;
    }
};