位操作集锦
- 异或运算
- 两两交换
- 数据签名
- 检测两个数是否拥有不同的符号，即一个正数，一个负数
- 寻找只出现一次的一个数字1
- 寻找只出现两次的一个数字
- 寻找只出现一次的一个数字2
- 寻找只出现一次的两个数字
- 与和位移运算
- 判断奇偶数
- 二进制数中1的个数
- 二进制数中最右边1的位置
- 其他小技巧
- 整数加1
- 求平均数
- 不用加减乘除做加法
- 设置第k位的值
异或运算
异或计算规则：
- 0 ^ 0 = 0
- 1 ^ 1 = 0
- 0 ^ 1 = 1 ^ 0 = 1
即 异或不等为1，相等为0
两两交换
当接触编程时，两两交换的代码模版如下：
int tmp = a;
a = b;
b = tmp;
使用异或的实现：
a = a ^ b;
b = a ^ b; //(a ^ b) ^ b = a
a = a ^ b; //(a ^ b) ^ a = b
感觉就是一种炫技，很少用。
数据签名
对原始数据按字节签名，签名值 = 对数据按字节异或。这种数据签名太简单用的较少。
检测两个数是否拥有不同的符号，即一个正数，一个负数
分析：正数符号位位0，负数符号位为1，两者异或时符号位为1
两者用于不同的符号: (num1 ^ num2) < 0
寻找只出现一次的一个数字1
- 问题：一个数组序列，除一个数字出现一次外，其他数字都出现两次，找到这个出现一次的数字。
- 解决方案：将数组中的所有数字异或，由于相同数字异或为0，所以最终结果就是只出现一次的数字。
int find_once_num(vector<int>& nums){
int result = 0;
for(int num: nums){
result ^= num;
}
return result;
}
寻找只出现两次的一个数字
- 问题：一个数组序列，除一个数字出现两次外，其他数字都出现一次，找到这个出现两次的数字。
- 解决思路：本质上将目标出现的次数转换为奇数次，其他非目标元素出现的次数转换为偶数次。
假设知道数组序列对应的不重复数字序列，将这些数字序列拼接到数组序列中，这样出现一次的数字在新序列中就出现两次，出现两次的数字在新序列中就出现三次，从而异或后的结果就是要查找只出现两次的数字。
int find_twice_num(vector<int>& nums){
int result = 0;
//假设nums对应的不重复的数字序列为[1,nums.size()]
for(int idx = 1; idx <= nums.size(); ++idx){
result ^= idx;
}
for(int num: nums){
result ^= num;
}
return result;
}
寻找只出现一次的一个数字2
- 问题描述：一个数组序列，除一个数字出现一次外，其他数字都出现三次，找到这个出现一次的数字。
- 分析：由于目标数字和其他数字都是奇数次，没法将目标数字变成奇数次，其他数字变成偶数次，这样就没法使用异或的思路了。这里除了使用hash统计数字外，还可以从另一个角度入手：位。
一个数字出现三次，那么某位为1时，一定该位出现会出现三次。这样每一位对3取余后的二进制位就是目标数字。
int find_once_num(vector<int>& nums){
int result = 0;
int length = sizeof(int) * 8;
for(int idx = 0; idx < length; ++idx) {
int sum = 0;
for(auto num: nums){
sum += ((num >> idx) & 1);
}
if(sum % 3 == 1){
result += (1 << idx);
}
}
return result;
}
寻找只出现一次的两个数字
- 问题描述：一个数组序列，除两个数字出现一次外，其他数字都出现两次，找到这两个出现一次的数字。
- 分析：该问题不能直接套用 寻找只出现一次的一个数字1 问题的解决方案，但是可以将其转换为 寻找只出现一次的一个数字1 问题。最好是能将原数组序列拆分为两个数组序列，每个数组序列中包含一个出现一次的数字，这样就可以在该序列中使用异或来找到出现一次的数字。那么如何拆分呢？
原数组序列进行异或后，等到的结果 = 出现一次的两个数字的异或，且该结果肯定不为0，即该结果的二进制中至少有一位为1，对应的出现一次的两个数字在该位一个为0，一个为1。因此可以使用该位来拆分原数组序列。
pair<int,int> find_once_num(vector<int>& nums){
int result = 0;
//对原始序列求值
for(auto num: nums){
result ^= num;
}
//找到最右侧1的位置
int idx = 0;
while((result & 1) == 0){
result >>= 1;
idx++;
}
int num1 = 0, num2 = 0;
for(auto num: nums){
//基于该位置进行分类
if((num >> idx) & 1){
num1 ^= num;
}else{
num2 ^= num;
}
}
return make_pair(num1,num2);
}
与和位移运算
与计算规则：
- 0 & 0 = 0
- 1 & 1 = 1
- 0 & 1 = 1 & 0 = 0
位移计算规则：
- 左移<<：右边补0，逻辑左移和算术左移一样。
- 右移>>：逻辑右移左边补0，算术右移左边补符号位。
在C/C++中，对于无符号数，可以认为是逻辑左移和逻辑右移。对于有符号数，可以认为是算术左移和算术右移。
#include <iostream>
using namespace std;
int main()
{
int num = 0x80000001;
//有符号数是算术右移：0x80000001,0xc0000000
cout << hex << num << "," << (num >> 1) << endl;
unsigned int unum = 0x80000001;
//无符号数是逻辑右移：0x80000001,0x40000000
cout << hex << unum << "," << (unum >> 1) << endl;
return 0;
}
判断奇偶数
分析：整数的二进制表示为 a n ∗ 2 n + a n − 1 ∗ 2 n − 1 + . . . + a 2 ∗ 2 2 + a 1 ∗ 2 1 + a 0 ∗ 2 0 a_n*2^n + a_{n-1}*2^{n-1} + ... +a_2 * 2^2+a_1 * 2^1 + a_0*2^0 an∗2n+an−1∗2n−1+...+a2∗22+a1∗21+a0∗20,其中 a i = 0 ∣ 1 a_i = 0|1 ai=0∣1。由表达式可知，当 a 0 = 0 a_0 = 0 a0=0时，该表达式 a n ∗ 2 n + a n − 1 ∗ 2 n − 1 + . . . + a 2 ∗ 2 2 + a 1 ∗ 2 1 = 2 ∗ ( a n ∗ 2 n − 1 + a n − 1 ∗ 2 n − 2 + . . . + a 2 ∗ 2 1 + a 1 ∗ 2 0 ) a_n*2^n + a_{n-1}*2^{n-1} + ... +a_2 * 2^2+a_1 * 2^1 = 2 * (a_{n}*2^{n-1} + a_{n-1}*2^{n-2} + ... +a_2 * 2^1+a_1 * 2^0 ) an∗2n+an−1∗2n−1+...+a2∗22+a1∗21=2∗(an∗2n−1+an−1∗2n−2+...+a2∗21+a1∗20)一定为偶数。
- 偶数：(num & 1) == 0
- 奇数：(num & 1) == 1
二进制数中1的个数
- 问题：给定一个无符号整数，求它的二进制表示中 1 的个数
- 解决方案1：n&1
通过不停的右移，统计最后一位是否为1，时间复杂度为O(32)
int getNum(unsigned int num) {
int cnt = num & 1;
while ((num >>= 1) != 0) {
cnt += num & 1;
}
return cnt;
}
- 解决方案2：n & (n-1)
n & (n - 1) 可以将最后一位置0，比如n = 5(101)，n - 1 = 4(100)，n & (n - 1) = 4(100)，从而置0的次数就是1出现的次数，时间复杂度为1出现的次数。
int getNum(unsigned int num) {
int cnt = 0;
while (num != 0) {
cnt++;
num &= (num-1)
}
return cnt;
}
注：n & (n - 1) 还可以用于判断数值n是否是2的整数幂，当 n & (n - 1) == 0时，说明n是2的整数幂。
- 解决方案3：大牛方案，二分法
采用二分法的思想，先计算每两位中 1 的个数，再计算每四位、每八位、每十六位，最后把两个十六位的个数相加。
int getNum(unsigned int num) {
//计算每两位中1的个数：最多2个1，需用2位bit
num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
//计算每四位中1的个数：最多4个1，需用3位bit
num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
//计算每八位中1的个数：最多8个1，需用4位bit
num = (num + (num >> 4)) & 0x0f0f0f0f;
//计算每十六位中1的个数：最多16个1，需用5位bit
num = num + (num >> 8);
//计算每三十二位中1的个数：最多32个1，需用6位bit
num = num + (num >> 16);
return num & 0x3f;
}
在处理过程中，首先将相邻位进行分组，然后对每分组进行处理：统一处理成低位相加，高位置零，利用二进制加法求和。
假设字节按位标号1,2,3,4,5,6,7,8，按两位分组为(1,2),(3,4),(5,6),(7,8)，每个分组最多2个1，占用2bit；按四位分组，则(1,2,3,4),(5,6,7,8)，每个分组最多4个1，占用3bit。
对于数值a=10010111，按两位分组(1,2),(3,4),(5,6),(7,8),即a=(10)(01)(01)(11)，每个分组内数值之和即为1的个数。
为了统计每个分组内1的个数，需要将1,3,5,7位右移一位，这样就可以利用二进制加法和2,4,6,8位上的数值相加，从而完成两两分组的统计。为了避免原1,3,5,7位的数值干扰，需要将其置零，使用0x5555 = 01010101可以将1,3,5,7位置0，即
第2,4,6,8位对应的值:a1 = 10010111 & 0x5555 = 00010101
第1,3,5,7位对应的值:a2 = (10010111 >> 1) & 0x5555 = 01001011 & 0x5555 = 01000001
a1 + a2 = 01010110，即每个分组中1的个数分别对应1、1、1、2。
二进制数中最右边1的位置
问题：给定一个无符号整数，求它的二进制表示中最右边1 的位置
int getBitSite(unsigned int num){
if(num == 0){
return 0;
}
int site = 1;
while((num&1) == 0){
num >>= 1;
site++;
}
return site;
}
扩展：如何只保留最右边的1，即除最右边的1保留外，其他位置的1置0？本质上就是清除最右边1左边的所有1。
- 方法1：n ^ (n & (n - 1))，n & (n - 1) 除最右边的1所在位置值为0外，其他位的值跟n一致，因此两者异或后就是结果
- 方法2：n & -n，负数采用补码的形式表示，即 -n = ~n + 1，这样-n在最右边1的左边跟n相反，在最右边1的右边跟n相同，两者与运算就是结果。比如n = 100100，则-n = -100100 = 011011 + 1 = 011100。
其他小技巧
整数加1
在计算机中，负数是采用补码表示的，补码 = 反码 + 1，即 -x = ~x + 1，因此有 x + 1 = - ~x 。
求平均数
常规计算方法: x + y 2 \frac {x+y} {2} 2x+y，在数学世界中，这种计算方法并没有问题，但在计算机世界中，这种写法就有问题。当x和y比较大时，会因计算机的存储溢出而导致结果不符预期。 x + y 2 = a + b 2 \frac {x+y} {2} = a + \frac {b} { 2} 2x+y=a+2b
- 优化方案1：当a = x, b = y - x,则有 x + y − x 2 x + \frac {y - x} {2} x+2y−x，该方案避免求和溢出
- 优化方案2：(x & y) + ((x ^ y) >> 1)
按照二进制表示 x + y 2 = ( x n + y n ) ∗ 2 n + ( x n − 1 + y n − 1 ) ∗ 2 n − 1 + . . . + ( x 1 + y 1 ) ∗ 2 1 + ( x 0 + y 0 ) ∗ 2 0 2 = ( x n + y n ) 2 ∗ 2 n + ( x n − 1 + y n − 1 ) 2 ∗ 2 n − 1 + . . . + ( x 1 + y 1 ) 2 ∗ 2 1 + ( x 0 + y 0 ) 2 ∗ 2 0 , 其中 x i , y i 分别对应 x 和 y 的二进制中对应位的值 \frac {x+y} {2} = \frac {(x_n + y_n) * 2 ^n + (x_{n-1} + y_{n-1}) * 2 ^{n-1} + ... + (x_1 + y_1) * 2 ^1 + (x_0 + y_0) * 2 ^0} {2} = \frac {(x_n + y_n)} {2} * 2 ^n + \frac {(x_{n-1} + y_{n-1})} {2}* 2 ^{n-1} + ... + \frac {(x_1 + y_1)} {2} * 2 ^1 + \frac {(x_0 + y_0)} {2} * 2 ^0,其中x_i,y_i分别对应x和y的二进制中对应位的值 2x+y=2(xn+yn)∗2n+(xn−1+yn−1)∗2n−1+...+(x1+y1)∗21+(x0+y0)∗20=2(xn+yn)∗2n+2(xn−1+yn−1)∗2n−1+...+2(x1+y1)∗21+2(x0+y0)∗20,其中xi,yi分别对应x和y的二进制中对应位的值，因此对上面的序列进行分类:
x i + y i = 0 ∣ 2 x_i+y_i = 0|2 xi+yi=0∣2组成序列：x & y
x i + y i = 1 x_i+y_i = 1 xi+yi=1组成序列：(x ^ y) >> 1
不用加减乘除做加法
int add(int a, int b){
//保留不用进位的二进制数
int num1 = a ^ b;
//找到需要进位的二进制数
int num2 = a & b;
num2 = num2 << 1;
//循环处理，一直到没有进位为止
if(num2 == 0){
return num1;
}
//使用进位后的数值 和 不需要进位的数值 相加
return add(num1, num2);
}
设置第k位的值
- 将第k位值置为1：n = n | (1 << (k - 1))
- 将第k位值置为0: n = n & ~(1 << (k - 1))
- 检查第k位值是否为1: (n & (1 << (k - 1))) != 0
- 切换第k位的值(即0变为1，1变为0)：n = n ^ (1 << (k - 1))
