LeetCode程式設計訓練 - 位運算(bit manipulation)
位運算基礎
說到與(&)、或(|)、非(~)、異或(^)、位移等位運算，就得說到位運算的各種奇淫巧技，下面分運算子說明。
1. 與(&)
計算式 a&b，a、b各位中同為 1 才為 1，否則為0，a&1和a%2效果一樣；來看兩道典型的題目，第1道計算整數二進位制中 1 的位數：
//191. Number of 1 Bits
int hammingWeight(uint32_t n) {
int res=0;
while(n!=0){
n=n&(n-1);
++res;
}
return res;
}
n=n&(n-1)代表去掉整數n二進位制中最左側為 1 的位，例如n=12，則：
n-> 1 1 0 0 & n-1-> 1 0 1 1 ------------------ 1 0 0 0
第2道判斷一個數是否為4的乘方數（不能用loop解）：
//342. Power of Four
bool isPowerOfFour(int num) {
if(num==INT_MIN) return false;
return !(num&(num-1)) && (num&0x55555555);
}
以上0x55555555的二進位制表示為……01010101 (偶數位為0、奇數位為1)，像這樣tricky的數還有：
0xaaaaaaaa : 10101010101010101010101010101010 (偶數位為1，奇數位為0） 0x33333333 : 00110011001100110011001100110011 (1和0每隔兩位交替出現) 0xcccccccc : 11001100110011001100110011001100 (0和1每隔兩位交替出現) 0x0f0f0f0f : 00001111000011110000111100001111 (1和0每隔四位交替出現) 0xf0f0f0f0 : 11110000111100001111000011110000 (0和1每隔四位交替出現)
相關LeetCode題：
201. Bitwise AND of Numbers Range 題解
2. 或(|)
計算式a|b，a、b各位中有一個為1則結果為1；來看一道題：有正整數n，求小於或等於n的2的最大乘方數（不能用loop解）：
int largest_power(ing N) {
N = N | (N>>1);
N = N | (N>>2);
N = N | (N>>4);
N = N | (N>>8);
N = N | (N>>16);
return (N+1)>>1;
}
看起來是不是相當tricky，其思路是用或運算將右邊位數置為1，例如n=01010，通過或操作n變為01111，則n+1為10000，所求為01000；更詳細解釋見這裡
相關LeetCode題：
898. Bitwise ORs of Subarrays 題解
3. 異或(^)
計算式a^b，a、b對應位相同為0，相異則為1；根據異或性質有a^a=0，a^0=a，利用該性質可解決136. Single Number：
//136. Single Number
int singleNumber(vector<int>& nums) {
int res=0;
for(auto x:nums) res^=x;
return res;
}
相關LeetCode題：
4. 位移
a<<1效果相當於a*2(不超出數值類型範圍情況下)，a>>1效果相當於a/2，位移常用於按位輪詢。
相關LeetCode題：
逐位計算結果
有意思的時當我們的目光放到bit的維度，一些問題可以按位來求解，例如169. Majority Element求陣列中出現次數大於一半的數：
//169. Majority Element
int majorityElement(vector<int>& nums) {
int mask=1,size=nums.size(),ret=0;
for(int i=0;i<32;i++){
int count=0;
for(int j=0;j<size;j++){
if(nums[j]&mask) count++;
if(count>size/2){
ret|=mask;//逐位計算結果break;
}
}
mask<<=1;
}
return ret;
}
相關LeetCode題：
477. Total Hamming Distance 題解
421. Maximum XOR of Two Numbers in an Array 題解
使用bit表示資料
在一些場景下我們希望用bit來表示資料，或節省空間或利用bit的運算特性來表示狀態轉換。