移位運(yùn)算
移位運(yùn)算包含邏輯移位(logical shif) 和 算術(shù)移位(arithmetic shift)壁公。
- 邏輯移位：移出去的位丟棄，空缺位用"0"填充奈揍。
- 算術(shù)移位：移出去的位丟棄曲尸，空缺位用"符號(hào)位"來填充。
左移操作
將 A 的二進(jìn)制表示的整體向左移 B 位男翰，左邊超出 32 位的截掉（包括符號(hào)位）另患，右邊不足的位補(bǔ) 0。
int A = 12
int C = A << B // C = A * 2^B（如果不溢出）
eg：溢出
INT_MAX // 01111111 11111111 11111111 11111111(補(bǔ)碼) = 2147483647
INT_MAX << 1 // 11111111 11111111 11111111 11111110(補(bǔ)碼) = -2 (邏輯移位)
UINT_MAX // 11111111 11111111 11111111 11111111 = 4294967295
UINT_MAX << 1 // 11111111 11111111 11111111 11111110 = 4294967294 (邏輯移位)
右移操作
C++ 里面蛾绎，右移操作和數(shù)據(jù)類型相關(guān)昆箕，無符號(hào)數(shù)是邏輯移位鸦列，有符號(hào)數(shù)是算術(shù)移位。
int A = 12
int C = A << B // C = A / 2^B
eg：
INT_MIN // 10000000 00000000 00000000 00000001(補(bǔ)碼) = -2147483648
INT_MIN >> 1 // 11000000 00000000 00000000 00000000(補(bǔ)碼) = -1073741824 (算術(shù)移位)
UINT_MAX // 11111111 11111111 11111111 11111111 = 4294967295
UINT_MAX >> 1 // 01111111 11111111 11111111 11111111 = 2147483647 (邏輯移位)
按位與操作 a & b
將A和B的二進(jìn)制表示的每一位進(jìn)行與操作鹏倘，只有兩個(gè)對(duì)應(yīng)的二進(jìn)制位都為1時(shí)薯嗤，結(jié)果位才為1，否則為0纤泵。這個(gè)常用來取出某個(gè)特定的二進(jìn)制位的值骆姐。
0 0 1 0 1 0
& 1 0 1 1 0 0
-------------------
0 0 1 0 0 0
按位或操作 a | b
將A和B的二進(jìn)制表示的每一位進(jìn)行或操作，只要兩個(gè)對(duì)應(yīng)的二進(jìn)制位有一個(gè)為1捏题，結(jié)果位就為1玻褪，否則為0。這個(gè)常用來將某個(gè)特定的二進(jìn)制位的值置1公荧。
0 0 1 0 1 0
| 1 0 1 1 0 0
-------------------
1 0 1 1 1 0
按位非操作 ~ a
將A的二進(jìn)制表示每一位進(jìn)行取反操作带射，如果對(duì)應(yīng)的二進(jìn)制位為0，結(jié)果位為1循狰，否則為0窟社。
0 0 1 0 1 0
~
-------------------
0 1 0 1 0 1
按位異或操作
將A和B的二進(jìn)制表示的每一位進(jìn)行異或操作，如果對(duì)應(yīng)的二進(jìn)制位不同晤揣，結(jié)果位為1桥爽，否則為0。
0 0 1 0 1 0
^ 1 0 1 1 0 0
-------------------
1 0 0 1 1 0
技巧1：不用加減乘除做加法昧识，乘法
-
不用加減乘除做加法：計(jì)算3 +６(不考慮溢出)
3: 0 0 1 1 6: 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 ^ 0 1 1 0 & 0 1 1 0 + 0 1 0 0(0010 << 1) ----------------- ---------------- ---------------- 0 1 0 1(不進(jìn)位) 0 0 1 0 (進(jìn)位) 1 0 0 1(9) 0 1 0 1 0 1 0 1 0 0 0 1 ^ 0 1 0 0 & 0 1 0 0 + 1 0 0 0(0100 << 1) ----------------- ---------------- ---------------- 0 0 0 1(不進(jìn)位) 0 1 0 0 (進(jìn)位) 1 0 0 1(9) 0 0 0 1 0 0 0 1 1 0 0 1 ^ 1 0 0 0 & 1 0 0 0 + 0 0 0 0(0000 << 1) ----------------- ---------------- ---------------- 1 0 0 1(不進(jìn)位) 0 0 0 0 (進(jìn)位) 1 0 0 1(9)int plusWithBitOperator(int num1, int num2) { int xor_result = 0; int and_result = 0; while(num2) { xor_result = num1 ^ num2; and_result = num1 & num2; num1 = xor_result; num2 = and_result << 1; } return xor_result; } -
不用加減乘除運(yùn)算符計(jì)算a = b * 9(不考慮溢出)
a = b * 9 = b*8 + b = b << 3 + b;int mulWithBitOperator(int num1){ return plusWithBitOperator(num1 << 3, num1); }
技巧2：消除二進(jìn)制中最右側(cè)的那個(gè)1
x = 1100
x - 1 = 1011
x & (x-1) = 1000
應(yīng)用1：用O（1）時(shí)間檢測整數(shù)n是否是2的冪次
- N如果是2的冪次钠四，那么N滿足2個(gè)條件
- N > 0
- N的二進(jìn)制表示中只有1個(gè)1。
因?yàn)槎M(jìn)制表示中只有一個(gè)1跪楞，所以N&(N-1)將N唯一的一個(gè)1消去缀去，應(yīng)該返回0。
bool checkPowerOf2(int n)
{
return n > 0 && (n & (n-1)) == 0;
}
應(yīng)用2：計(jì)算在32位整數(shù)的二進(jìn)制表示中有多少個(gè)1
由x & (x - 1)消去x最后一位的1可知甸祭。不斷使用 x & (x - 1) 消去x最后一位的1缕碎，計(jì)算總共消去了多少次即可。
int countBinaryOnes(int num)
{
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
應(yīng)用3：如果要將整數(shù)A轉(zhuǎn)換為B池户，需要改變多少個(gè)bit位咏雌？
異或操作，相同為0校焦，相異為1赊抖，所以問題轉(zhuǎn)變成了計(jì)算A異或B之后這個(gè)數(shù)中1的個(gè)數(shù)。
countBinaryOnes(a ^ b);
技巧3：巧用異或運(yùn)算
- 一個(gè)數(shù)同另一個(gè)數(shù)異或2次還等于它本身寨典。
a ^ b ^ b = a
b ^ b = 0
應(yīng)用1：數(shù)組中氛雪，只有一個(gè)數(shù)出現(xiàn)一次，剩下都出現(xiàn)兩次耸成，找出出現(xiàn)一次的數(shù)
因?yàn)橹挥幸粋€(gè)數(shù)恰好出現(xiàn)一個(gè)报亩，剩下的都出現(xiàn)過兩次浴鸿，所以只要將所有的數(shù)異或起來，就可以得到唯一的那個(gè)數(shù)弦追，因?yàn)橄嗤臄?shù)出現(xiàn)的兩次岳链，異或兩次等價(jià)于沒有任何操作！
int singleNumber(int[] nums)
{
int result = 0, n = nums.length;
for (int i = 0; i < n; i++) {
result ^= nums[i];
}
return result;
}
應(yīng)用2：數(shù)組中劲件，只有一個(gè)數(shù)出現(xiàn)一次宠页，剩下都出現(xiàn)三次，找出出現(xiàn)一次的數(shù)
應(yīng)用3：數(shù)組中寇仓，只有兩個(gè)數(shù)出現(xiàn)一次，剩下都出現(xiàn)兩次烤宙，找出出現(xiàn)一次的這兩個(gè)數(shù)
有了第一題的基本的思路遍烦，我們可以將數(shù)組分成兩個(gè)部分，每個(gè)部分里只有一個(gè)元素出現(xiàn)一次躺枕，其余元素都出現(xiàn)兩次服猪。那么使用這種方法就可以找出這兩個(gè)元素了。不妨假設(shè)出現(xiàn)一個(gè)的兩個(gè)元素是x拐云，y罢猪，那么最終所有的元素異或的結(jié)果就是等價(jià)于res = x^y。并且res叉瘩！=0
對(duì)于x和y膳帕，一定是其中一個(gè)這一位是1，另一個(gè)這一位不是1薇缅，因?yàn)槿绻际?或者都是1危彩，怎么可能異或出1
對(duì)于原來的數(shù)組，我們可以根據(jù)這個(gè)位置是不是1就可以將數(shù)組分成兩個(gè)部分泳桦。x汤徽，y一定在不同的兩個(gè)子集中。
先講個(gè)小技巧
10：01010 (補(bǔ)碼灸撰，最高位為符號(hào)位)
-10：10101(反碼谒府，正數(shù)的反碼就是原碼，負(fù)數(shù)的反碼是符號(hào)位不變浮毯，其余位取反)
-10：10110（補(bǔ)碼完疫，正數(shù)的補(bǔ)碼就是原碼，負(fù)數(shù)的補(bǔ)碼是反碼+1）
n &= -n; // n中最后一位為1的位為1亲轨，其余位為0
0 1 0 1 0
& 1 0 1 1 0
----------------
0 0 0 1 0
vector<int> singleNumber(const vector<int>& vec) {
int diff = 0;
for (const auto &i : vec)
diff ^= i;
// 取出最后一位為1的位置
diff &= -diff;
vector<int> vec={0, 0};
for (int i = 0; i < nums.lenght; i++) {
if ((nums[i] & diff) == 0)
vec[0] ^= nums[i];
else
vec[1] ^= nums[i];
}
return vec;
}
不用額外空間使用異或交換2個(gè)元素
異或運(yùn)算的特質(zhì)：
如果a ^ b = c趋惨，那么a ^ c = b 與 b ^ c = a同時(shí)成立，利用這一條惦蚊，于是交換2個(gè)變量的值有以下方法：
a = a ^ b
b = a ^ b
a = a ^ b
- 使用加減法交換2個(gè)變量值也可以達(dá)到不用額外空間交換2個(gè)變量的值
a = a + b // new_a = old_a + old_b b = a - b // new_b = new_a - old_b = old_a + old_b - old_b = old_a a = a - b // new_a = new_a - new_b = old_a + old_b - old_a
技巧4：循環(huán)隊(duì)列的buffer size 為什么需要保證為2的冪器虾？
為什么需要保證 buffer size 為2的冪讯嫂？
因?yàn)橥ǔＱh(huán)隊(duì)列的入隊(duì)和出隊(duì)操作要不斷的對(duì)size進(jìn)行求余， 為了提高效率兆沙，將 buffer size 擴(kuò)展為2的冪欧芽，就可以使用位運(yùn)算。kfifo->in % kfiifo->size 等同于 kfifo->in & (kfifo->size – 1)葛圃。
假設(shè)現(xiàn)在size 為16：
8 & (size - 1) = 01000 & 01111 = 01000 = 8
15 & (size -1) = 01111 & 01111 = 01111 = 15
16 & (size - 1) = 10000 & 01111 = 00000 = 0
26 & (size - 1 ) = 11010 & 01111 = 01010 = 10
所以保證size是2的冪的前提下千扔，可以通過位運(yùn)算的方式求余，在頻繁操作對(duì)列的情況下可以大大提高效率库正。
參考資料
[1] https://www.jiuzhang.com/tutorial/bit-manipulation/75
[2] http://blog.sina.cn/dpool/blog/s/blog_bf30105b0101gk68.html
