本文主要讲使用位运算的一些技巧。
位运算
位运算符号
| 符号 | c/cpp | python | 含义 |
|---|---|---|---|
| 按位与 | a & b | a & b | 1 & 1 = 1, 1 & 0 = 0, 同1为1, 有0为0 |
| 按位或 | a | b | a | b | 1 | 1 = 1, 1 | 0 = 1, 有1为1, 同0为0 |
| 按位异或 | a ^ b | a ^ b | 1 ^ 1 = 0, 1 ^ 0 = 1, 相同位不同为1, 相同为0 |
| 按位取反 | ~a | ~b | ~1 = 0, ~0 = 1 |
| 左移 | a << b | a << b | 把a转化为二进制后向左移b位, 高位丢弃, 低位补零 |
| 右移 | a >> b | a >> b | 把a转化为二进制后向右移b位, 去掉后b位 |
优先级
在c/cpp中优先级(只有位运算的优先级) 运算符优先级
| 1 | ~ |
|---|---|
| 2 | <<、>> |
| 3 | & |
| 4 | ^ |
| 5 | | |
| 6 | &=、^=、|=、<<=、>>= |
奇技淫巧
按位与
/*
判断奇偶, n & 1
if (n & 1) {
odd(奇数);
} else {
even(偶数);
}
清空最低位的1 ---> n & (n - 1)
n & (n - 1)还可以判断一个数是不是2的幂
bool isPowerOfTwo(int n) {
return n > 0 ? (n & (n - 1)) == 0 : false;
}
得到最低位的1 ---> n & -n
n & ~n = 0
*/191. 位1的个数 汉明重量
按位异或
/*
x ^ 0 = x;
x ^ 1 = -x;
x ^ (~x) = 1;
x ^ x = 0;
// 交换两个数
a ^= b;
b ^= a;
a ^= b;
一个字符异或上(1 << 5)即32, 可以实现大小写转换(即大写变小写,小写变大写)
char ch = 'a'; // ch = 'A'
a ^= (1 << 5)
cout << "a = " << a << endl;
>>> a = 'A' // 'a'
*/解释下其中几个
x ^ ~0 = ~x
相当于x的每一位都异或了1，那原本是1的位都变成了0，原本是0的位都变成了1。
x ^ ~x = ~0
x与~x的每一位肯定不相同，所以异或出来就是1。
a ^= b; b ^= a; a ^= b;
/*
a ^= b ---> a = a ^ b;
b ^= a ---> b = b ^ (a ^ b) = b ^ b ^ a = 0 ^ a = a;
a ^= b ---> a = (a ^ b) ^ a = a ^ a ^ b = 0 ^ b = b;
*/根据异或的性质容易得知，奇数个1异或为1， 偶数个1异或为0
推广 —> 奇数个相同的数异或为这个数，偶数个相同的数异或为0
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
来源：力扣（LeetCode）
我们知道出现了偶数次的数字，最后肯定会抵消掉，2 ^ 2 = 0， 而奇数次的肯定会保留。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (auto &num : nums) {
ans ^= num;
}
return ans;
}
};左移
/*
一个数左移一位×2，左移n位×2的n次方
*/右移
/*
一个数字右移一位÷2，右移n位÷2的n次方
取中间值 int mid = (left + right) >> 1
*/混合起来的一些技巧
/*
将x最右边的n位清0, x & (~0 << n)
获取x的第n值, (x >> n) && 1
获取x的第n位的幂值, x & (1 << (n - 1))
仅将第n位置为1, x | (1 << n)
仅将第n位置为0, x & (~(1 << n))
将x最高位至第n位(含)清0, x & ((1 << n) - 1)
将第n位至第0位(含)清0, x & (~((1 << (n + 1)) - 1))
*/总结
位运算用好了还是挺强的，面试还挺喜欢出的 ，老规矩，熟能生巧。
更多奇技淫巧可以参考 优秀程序员不得不知道的20个位运算技巧
