神奇的位运算
运算符介绍
| 运算符 | 操作 | 介绍 |
|---|---|---|
| & | 与 | 位数据的值同为1，该位取1，不同取0 |
| | | 或 | 位数据两者有一个为1，该位取1，否则取0 |
| ~ | 非 | 对位数据取反 |
| ^ | 异或 | 两者位数据不同取1，否则取0 (0^n = n n为任意数) |
| << | 左移 | 左移后右边位补0 |
| >> | 右移 | 右移后左边位补0 |
运算小技巧
1、判断奇偶数
常规思路：
if(n % 2 == 1) //n为奇数
位运算技巧：
-- 利用&运算符，与1进行运算，其它位数据均为0
if(n & 1 == 1) //n为奇数
2、交换两个数字
常规思路：
//a和b交换
int temp = a;
a = b;
b = temp;
-- 使用异或^运算，相同的两个数异或结果为0：
//a和b交换
a = a^b; // a = a^b
b = a^b; // b = (a^b)^b = a
a = a^b; // a = (a^b) ^ (a^b)^b
假设a = 5, b = 7,推导过程见注释：
3、统计数字二进制表示中1的个数
-- 使用移位计算：
public int GetNumber1InBinary(int num){
int res = 0;
for(int i = 0; i< 32; i++){
if(num & (1 << i) != 0){
res++;
}
}
return res;
}
4、只出现一次的一个数字
例如：1, 2, 3, 5, 3, 2中，仅有只有一个1,其它数字都是2个；
--使用异或运算，两个相同的数字异或为0，任何数字与0异或还是其自身。
public int GetSingleNumber(int[] nums){
int res = 0;
foreach(var num in nums){
res ^= num;
}
return res;
}
5、只出现一次的一个数字(升级版)
例如：将上题中其它数字都改为3个，则将无法使用异或运算直接运算：
这次利用整除求余，先看图：
即，每位总会多出一个0或1不满足是3的倍数，循环完将各位数据求和便可得到最终的答案，这样的时间复杂度为O(n).
public int GetSingleNumber(int[] nums){
int res = 0;
for(int i = 0; i< 32; i++){
int sum = 0;
for(var num in nums){
if(((num > 1) & 1) == 1){
sum++;
}
}
if(sum % 3 == 0){
res += (1<