力扣君表示位运算也是各大互联网公司面试经常会问的一类问题。
计算机中的数在内存中都是以二进制形式进行存储的,用位运算就是直接对整数在内存中的二进制位进行操作,因此其执行效率非常高,在程序中尽量使用位运算进行操作,这会大大提高程序的性能。
位操作符
1 0 0 1 1
& 1 1 0 0 1
------------------------------
1 0 0 0 1
1 0 0 1 1
| 1 1 0 0 1
------------------------------
1 1 0 1 1
1 0 0 1 1
^ 1 1 0 0 1
-----------------------------
0 1 0 1 0
~ 1 0 0 1 1
-----------------------------
0 1 1 0 0
int a = 8;
a << 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位后:0000 0000 0000 0000 0000 0000 0100 0000
>> 右移运算,向右进行移位操作,对无符号数,高位补 0,对于有符号数,高位补符号位,如
unsigned int a = 8;
a >> 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位后:0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
移位前:1111 1111 1111 1111 1111 1111 1111 1000
移位前:1111 1111 1111 1111 1111 1111 1111 1111
常见位运算问题
1. 位操作实现乘除法
int a = 2;
a >> 1; ---> 1
a << 1; ---> 4
2. 位操作交货两数
//普通操作
void swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
//位与操作
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
位与操作解释:第一步:a ^= b ---> a = (a^b);
第二步:b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a
第三步:a ^= b ---> a = (a^b)^a = (a^a)^b = b
3. 位操作判断奇偶数
if(0 == (a & 1)) {
//偶数
}
4. 位操作交换符号
int reversal(int a) {
return ~a + 1;
}
整数取反加1,正好变成其对应的负数(补码表示);负数取反加一,则变为其原码,即正数
5. 位操作求绝对值
int abs(int a) {
int i = a >> 31;
return i == 0 ? a : (~a + 1);
}
上面的操作可以进行优化,可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况,即 i = 0 为正,i = -1 为负。对于任何数与 0 异或都会保持不变,与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i),即整数时 a 与 0 异或得到本身,再减去 0,负数时与 0xffffffff 异或将 a 进行取反,然后在加上 1,即减去 i(i =-1)
int abs2(int a) {
int i = a >> 31;
return ((a^i) - i);
}
6. 位操作进行高低位交换
34520的二进制表示:
10000110 11011000
将其高8位与低8位进行交换,得到一个新的二进制数:
11011000 10000110
其十进制为55430
从上面移位操作我们可以知道,只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位,高位补 0;将 a<<8 即可将 低 8 位移到高 8 位,低 8 位补 0,然后将 a>>8 和 a<<8 进行或操作既可求得交换后的结果。
unsigned short a = 34520;
a = (a >> 8) | (a << 8);
7. 位操作进行二进制逆序
将无符号数的二进制表示进行逆序,求取逆序后的结果,如
数34520的二进制表示:
10000110 11011000
逆序后则为:
00011011 01100001
它的十进制为7009
在字符串逆序过程中,可以从字符串的首尾开始,依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理,这里我们分组进行多步处理。
交换前: 10 00 01 10 11 01 10 00
交换后: 01 00 10 01 11 10 01 00
交换前: 0100 1001 1110 0100
交换后: 0001 0110 1011 0001
交换前: 00010110 10110001
交换后: 01100001 00011011
交换前: 0110000100011011
交换后: 0001101101100001
对于上面的第一步,依次以 2 位作为一组,再进行组内高低位交换,这样处理起来比较繁琐,下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位,将空余位用 0 填充:
原数: 10000110 11011000
奇数位: 10000010 10001000
偶数位: 00000100 01010000
再将奇数位右移一位,偶数位左移一位,此时将两个数据相或即可以达到奇偶位上数据交换的效果:
原数: 10000110 11011000
奇数位右移一位: 0 10000010 1000100
偶数位左移一位:0000100 01010000 0
两数相或得到: 01001001 11100100
上面的方法用位操作可以表示为:
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理,可以得到其第二、三和四步为:
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整个操作为:
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
8. 位操作统计二进制中 1 的个数
统计二进制1的个数可以分别获取每个二进制位数,然后再统计其1的个数,此方法效率比较低。这里介绍另外一种高效的方法,同样以 34520 为例,我们计算其 a &= (a-1)的结果:
count = 0
while(a){
a = a & (a - 1);
count++;
}
欢迎各位知友关注力扣官方微信公众号:「 LeetCode力扣 」,更多关于程序员面试、技术干货的内容等你来啃!