位运算的高级应用
位运算符: 针对整数的二进制.下面的数据假设为1字节(实际为4字节)
12 0000 1100
13 0000 1101
12 & 13 0000 1100 按位与,相同的位都为1才为1
12 | 13 0000 1101 按位或,相同的位只要有一个为1就为1
12^13 0000 0001 按位异或,相同的位不一样才为1,否则为0
~12 1111 0011 按位取反,原来的位为1则取反为0,为0则取反为1
12<<1 000 11000 24 = 122 按位左移,右边补0
12<<2 00 110000 48=124
12>>1 00000 110 6=12/2 按位右移,左边补符号位
(无符号补0,有符号且符号位为1补1,有符号且符号位为0补0)
12>>2 000000 11 3=12/4
注意 -1>>2 111111 11 -1
下面这种题的解题思路是:
第一步.确定符号(用|,^还是&)
其中对一位数字的操作
变1:|1
变0:&0
取反:^1
第二步.确认数字
第三步.构造数字
举例说明如下:
去掉最后一位 | (101101->10110) | x >> 1
在最后加一个0 | (101101->1011010) | x << 1
在最后加一个1 | (101101->1011011) | (x << 1)|1
把最后一位变成1 | (101100->101101) | x | 1
把最后一位变成0 | (101101->101100) | (x | 1)-1
最后一位取反 | (101101->101100) | x ^ 1
把右数第k位变成1 | (101001->101101,k=3) | x | (1 << (k-1))
把右数第k位变成0 | (101101->101001,k=3) | x & ~(1 << (k-1))
右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1))
取末三位 | (1101101->101) | x & 7
取末k位 | (1101101->1101,k=4) | x & ((1 << k)-1)
取右数第k位 | (1101101->1,k=4) | (x >> (k-1)) & 1