C++ 位操作

按位与运算符&

运算规则:有0为0,全1为1

即:

1
2
3
4
0 & 0 = 0;
0 & 1 = 0;
1 & 0 = 0;
1 & 1 = 1;

负数按补码的形式参加按位与运算

“与运算”的特殊用途:

(1)清零

如果想将一个单元清零,即使其全部二进制位为0,只要与一个各位都为零的数值相与,结果为零。

(2)取一个数中的指定位

找一个数,对应X要取的位,该数的对应位为1,其余位为零,此数与X进行“与运算”可以得到X中的指定位。

例如:X=10101110

要取X的低四位,用 X & 0000 1111 = 0000 1110即可得到。

按位或运算符|

运算规则:有1为1,全0为0

即:

1
2
3
4
0 | 0 = 0;
0 | 1 = 1;
1 | 0 = 1;
1 | 1 = 1;

“或运算”的特殊用途:

(1)常用来把一个数的某些位置1

方法:找到一个数,对应X要置1的位,该数的对应位为1,其余位为零。此数与X“相或”可使X中的某些位置1。

例:将X=10100000的低4位置1 ,用 X | 0000 1111 = 1010 1111即可得到。

异或运算符^

运算规则:相同为0, 不同为1

即:

1
2
3
4
0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

”异或“运算的特殊作用:

(1)使特定位翻转 ,找一个数,对应X要翻转的各位,该数的对应位为1,其余位为零,此数与X对应位异或即可。

例:X=10101110,使X低4位翻转,用X ^ 0000 1111 = 1010 0001即可得到。

(2)与0相异或,保留原值 ,X ^ 0000 0000 = 1010 1110。

取反运算符~

运算规则:0变1,1变0

即:

1
2
~1 = 0;
~0 = 1;

“取反”运算的特殊作用

使一个数的最低位为零,可以表示为:a & ~1。

~1的值为1111111111111110,再按“与”运算,最低位一定为0。因为“~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

左移运算符(<<)

将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。

例:a = a << 2 将a的二进制位左移2位,右补0,

左移1位后a = a * 2;

若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2。

右移运算符(>>)

将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。

操作数每右移一位,相当于该数除以2。

例如:a = a >> 2 将a的二进制位右移2位,

左补0 or 补1 得看被移数是正还是负。

模拟二进制加法

使用异或,按位与和移位操作可以模拟二进制的加法过程

1
2
3
4
5
6
7
8
int add(int a, int b) {
while(b != 0) {
auto temp = (unsigned int)(a & b) << 1;
a = a ^ b;
b = temp;
}
return a;
}

C++不支持负数的移位,因此需要加上转换为非负数后操作。

java则可以适用负数

1
2
3
4
5
6
7
8
9
10
public int add(int a, int b) {
int m = a ^ b; //不进位加法
int n = (a & b) << 1; //进位
while (n != 0) {
int temp = n ^ m;
n = (m & n) << 1;
m = temp;
}
return m;
}