[Leetcode] Theme：Bit-Manipulation

括號

所有 bitwise 操作都建議要特別注意括號，一來增加易讀性、二來避免 bug 的產生

(n&1)

判斷 n 之最右位 (rightmost bit) 是否為 1

(n&(1<<(k-1))) or (n>>(k-1)&1)

承上判斷 n 之右邊數來第 k 位 (rightmost k bit) 是否為 1

(n&mask)

承上判斷 n 之 mask 中位置是否為 1，可參考 『342. Power of Four』，其為確認唯一的 1 是否位在偶數位上，故會使用 0x5555 5555 的 mask；奇數位則可用 0xaaaa aaaa 的 mask

相鄰兩 bit

可用 (n&1) 與 ((n>>1)&1) 來表示相鄰兩位置

(n&(n-1)) 與 『是否為 2 之指數倍』

表示『將最右位的 1 改為 0 之操作』

n (十進位)	n (二進位)	n-1 (十進位)	n-1 (二進位)	n&n-1 (二進位)	n&n-1 (十進位)
1	0001	0	0000	0000	0
2	0010	1	0001	0000	0
3	0011	2	0010	0010	2
4	0100	3	0011	0000	0
5	0101	4	0100	0100	4
6	0110	5	0101	0100	4
7	0111	6	0110	0110	6
8	1000	7	0111	0000	0

且可觀查到，其中 2 的指數倍計算出之結果皆為 0，原因為將最右邊之 1 改成 0 的操作，將會把 2 的指數倍歸零，故要確認是否為 2 的指數倍，也可以透過 if (n&(n-1) == 0) 來判斷

• 需注意 “n&(n-1) == 0” 不等於 “(n&(n-1)) == 0”，後者才是正確的，前者會有優先判斷 tmp = ((n-1) == 0)，而後 n&tmp 結果之錯誤狀況

// n=2 之舉例
cout << ((n-1) == 0) << endl;       // 2-1!=0 -> 0
int tmp = ((n-1) == 0);             // tmp = 0
cout << tmp << endl;                // 0
cout << (n&(n-1) == 0) << endl;     // 0
cout << ((n&(n-1)) == 0) << endl;   // 1

二進位位數 / 長度

int numberOfBits(int n) {
      return log2(n) + 1;
}

__builtin_popcount()

用以計算 n 以二進位表示下有幾個 1；另外需注意不同型別下使用內建函式需調整
__builtin_popcount() = int
__builtin_popcountl() = long int
__builtin_popcountll() = long long

long long k=-1;
cout << __builtin_popcount(k) << endl;      // 32
cout << __builtin_popcountl(k) << endl;     // 64
cout << __builtin_popcountll(k) << endl;    // 64，LC 最大即 64 bits

位置

以 int 32 位元來說，若有需要操作每一位時，可以開一長度為 32 之 vector 來存 (vector bit(32);)，但有時候可以直接拿一個 cnt 來進行位元運算 (&, |)，可參考 『2401. Longest Nice Subarray』 或 『2680. Maximum OR』 此題之解法，其分別有 & 與 | 之 prefix / sufix 概念的展示

『2411. Smallest Subarrays With Maximum Bitwise OR』 即是透過 (類) 前綴和之概念來加速解之

int test(){                     // 回傳目前前綴和之結果
    int res=0;
    for (int i=0; i<32; i++){
        res <<= 1;
        res += !!(bit[i]);
    }
    return res;
}
void cal(int k, int sign){      // 計算更新後之結果，可加入數值或刪除數值
    for (int i=31; i>-1; i--){
        bit[i] += (k&1)*sign;
        k >>= 1;
    }
}

subarray for & 與 |

利用 (類) 前綴和與 (類) DP 的概念縮減運算量，參見 『898. Bitwise ORs of Subarrays』 與 『1521. Find a Value of a Mysterious Function Closest to Target』

int subarrayBitwiseORs(vector<int>& arr) {
    unordered_set<int> ret, cur, nxt;
    for (auto c: arr){
        nxt.clear();
        nxt.insert(c);
        for (auto k: cur){
            nxt.insert(k|c);
        }
        cur.swap(nxt);
        for (auto k: cur) ret.insert(k);
    }
    return ret.size();
}

XOR (^)

取反，0 -> 1, 1 -> 0 的概念，以整數來說也可以用 !c 表示 (c=0 or 1)；其相關變化相當多，亦是重要觀念

swap

void swap(int &a, int &b){
    a ^= b;
    b ^= a;
    a ^= b;
}

0 到 n 數字之 xor

具有 mod 4 後餘數特性，可參見 1486 題 O(1) 解法

int sumXor(int x){
    if (x%4==0) return x;
    else if (x%4==1) return 1;
    else if (x%4==2) return x+1;
    return 0;
}

或異之 (類) 前綴和特性

xor 具有類似前綴和的特性，若要求 k^(k+1)…^(n-1)n，等於 (1^…n) ^ (1^…k) 之結果

string to decimal

int / long int 可用 strtol
long long 可用 strtoll
unsigned long 可用 strtoul
其末位表示原 string 使用的是哪種進位

// s = "101"
int tmp = strtol(s.c_str(), NULL, 2);               // 5
long int tmp = strtol(s.c_str(), NULL, 2);          // 5
long long tmp = strtoll(s.c_str(), NULL, 2);        // 5
unsigned long tmp = strtoul(s.c_str(), NULL, 2);    // 5

// s = "11111111111111111111111111111111"
int tmp = strtol(s.c_str(), NULL, 2);               // -1
unsigned int tmp = strtol(k.c_str(), NULL, 2);      // 4294967295

1863. Sum of All Subset XOR Totals

本題的 O(n) 解法因非常特殊，故特別例之
n 個數之子集共有 2^n 種，任一一個元素的某一 bit 若為 1，則會貢獻出 2^(n-1) 次結果；故利用 | 來判斷給定具影響力 / 1 的結果於該位，最終 shift n-1 位即可得總和

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n=nums.size();
        int ans=0;
        for (int i=0; i<n; i++){
            ans |= nums[i];
        }
        return ans << (n-1);
    }
};

421. Maximum XOR of Two Numbers in an Array

透過 Trie 來反查最大結果，延申題請見 『2935. Maximum Strong Pair XOR II』

class Solution {
    class TrieNode{
        public:
            TrieNode* next[2];
    };
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        for (auto c: nums){
            TrieNode* node=root;
            for (int i=31; i>-1; i--){
                if (node->next[(c>>i)&1] == NULL)
                    node->next[(c>>i)&1] = new TrieNode();
                node = node->next[(c>>i)&1];
            }
        }

        int mxv=0;
        for (auto c: nums){
            TrieNode* node = root;
            int res=0;
            for (int i=31; i>-1; i--){
                if (node->next[1-(c>>i)&1] != NULL){
                    node = node->next[1-(c>>i)&1];
                    res = (res<<1)+1;
                }
                else{
                    node = node->next[(c>>i)&1];
                    res = (res<<1);
                }
            }
            mxv = max(mxv, res);
        }
        return mxv;
    }
};

2571. Minimum Operations to Reduce an Integer to 0

利用加上 (1<<k) 與 __builtin_popcount 判斷是否減少位數，進而操作

透過乘負一來標記數 (類 xor)

參見 『645. Set Mismatch』 或 『287. Find the Duplicate Number』 之 TC = O(n) + SC = O(1) 的解法

// 645. Set Mismatch
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int missing,repeat;
        for(int i=0;i<nums.size();i++){
            if(nums[abs(nums[i])-1]<0) repeat=abs(nums[i]);
            else nums[abs(nums[i])-1]*=-1;
        }

        for(int i=0;i<nums.size();i++){
            if(nums[i]>0) missing=i+1;
        }

        return {repeat,missing};
    }
};

加法器

從傳統的一位加法器可知道 sum = a^b, carry = a&b，將數的每個位置獨立思想，即可得到以下程式，且 carry 位需進位，而操作直至無進位為主，即 『371. Sum of Two Integers』

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
    return a;
    }
};

加減 1 與負號

void add_one(int x) {
    return -~x;         // x++
}
 
void sub_one(int x) {
    return ~-x;         // x--
}

void negative(int x) {
    return ~x+1;        // -x;
}

void negative(int x) {
    return (x^-1)+1;    // -x;
}

題單

靈神
官神
Leetcode