常見位運算操作總結：
- 基礎位運算
&：有0則為0
|：有1則為1
^：相同為0，相異為1 / 無進位相加- 運算符的優先級
管它什么優先級，加括號就完事兒了- 給一個數 n，確定它的二進制表示中的第 i (默認是從右起第0位) 位是 0 還是 1
(n >> i) & 1- 將一個數 n 的二進制表示的第 i 位修改為 1
n |= (1 << i)- 將一個數 n 的二進制表示的第 i 位修改成 0
n &= (~(1 << i))- 提取一個數 n 二進制表示中最右側的 1 （lowbit操作）
n & (-n)
(-n) 將 n 最右側的 1 的 左邊的區域 全部變成了相反的位- 干掉一個數 n 二進制表示中最右側的 1
n &= (n - 1)
(n - 1) 將 n 最右側的 1 的 右邊的區域(包括最右側的1)，全部變成了相反的位- 異或 ^ 運算的運算律
n ^ 0 = n
n ^ n = 0- 消消樂
a ^ b ^ c = a ^ (b ^ c)
根據第6、7條位運算操作，可以搞定1-3題。
- 位1的個數
int hammingWeight(int n)
{int ret = 0;while(n){++ret;n &= (n - 1);}return ret;
}
- 比特位計數
int hammingWeight(int n)
{int ret = 0;while(n){++ret;n &= (n - 1);}return ret;
}
vector<int> countBits(int n)
{vector<int> ret(n + 1);for(int i = 1; i <= n; ++i){ret[i] = hammingWeight(i);}return ret;
}
- 漢明距離
int hammingWeight(int n)
{int ret = 0;while(n){++ret;n &= (n - 1);}return ret;
}
int hammingDistance(int x, int y)
{int ret = 0;while(x && y){if((x & (-x)) < (y & (-y))){++ret;x &= (x - 1);}else if((x & (-x)) > (y & (-y))){++ret;y &= (y - 1);}else{x &= (x - 1);y &= (y - 1);}}ret += hammingWeight(x);ret += hammingWeight(y);return ret;
}
結合第 8 條位運算操作，可以搞定4-5題。
4. 只出現一次的數字
int singleNumber(vector<int>& nums)
{int ret = 0;for(int e : nums) ret ^= e;return ret;
}
- 只出現一次的數字 III
vector<int> singleNumber(vector<int>& nums)
{long long lowbit = 0;for(int e : nums) lowbit ^= e;lowbit &= (-lowbit);long long low_0 = 0, low_1 = 0;for(int e : nums){if(e & lowbit) low_1 ^= e;else low_0 ^= e;}return {(int)low_0, (int)low_1};
}
- 判定字符是否唯一
bool isUnique(string astr)
{if(astr.size() > 26) return false;int hash = 0;for(char c : astr){int bit = 1 << (c - 'a');if( hash & bit ) return false;else hash |= bit;}return true;
}
- 丟失的數字
// 高斯求和
int missingNumber(vector<int>& nums)
{int n = nums.size();int sum = (0 + n) * (n + 1) / 2;for(int e : nums) sum -= e;return sum;
}// 異或 運算律
int missingNumber(vector<int>& nums)
{int n = nums.size();int ret = 0;for(int i = 0; i <= n; ++i) ret ^= i;for(int e : nums) ret ^= e;return ret;
}
- 兩整數之和
int getSum(int a, int b)
{while(b){int no_carry = a ^ b;int carry = (a & b) << 1;a = no_carry;b = carry;}return a;
}
- 只出現一次的數字 II
int singleNumber(vector<int>& nums)
{int ret = 0;for(int i = 0; i < 32; ++i){int num = 0;for(int e : nums) if( e & (1 << i) ) ++num;if(num % 3) ret |= (1 << i);}return ret;
}
- 消失的兩個數字
vector<int> missingTwo(vector<int>& nums)
{int n = nums.size();int N = n + 2;int num = 0;for(int i = 1; i <= N; ++i) num ^= i;for(int e : nums) num ^= e;int lowbit = num & (-num);int low_0 = 0, low_1 = 0;for(int i = 1; i <= N; ++i){if(i & lowbit) low_1 ^= i;else low_0 ^= i;}for(int e : nums){if(e & lowbit) low_1 ^= e;else low_0 ^= e;}return {low_0, low_1};
}
)
