常见的位运算

基础运算

~ （取反）

| （或）

& （与）

^ （异或）

1
2
3
4
5
6
//取相反数，`e = ~ a + 1`
int g = 0b0001010;
int h = 0b0001100;
cout << (g | h); //或运算，每一位只要有一位有1，就能够保留
cout << (g & h); //与运算，只有两位都是1，才可以保留
cout << (g ^ h); //异或，相同就是0，不同就是1

<< （左移）

1
2
3
4
5
//整体状态向左移动,用0补右边
int i = 0b0011010;
cout << (i << 1);
//000000'1101'0
//00000'1101'00

>> , >>>（右移）

1
2
3
4
5
6
//对非负数效果一样,向右移,并且用0来补充左边
//而对负数效果不一样
//'>>'用符号位来补;'>>>'一律用0来补位
//1111 0000 0000 (分别向右移动2位)
//1111 1100 0000 
//0011 1100 0000

数学性质

  1. 对于非负数来说:
  • 非负数 << i ，等同于乘以2的i次方
  • 非负数 >> i ，等同于除以2的i次方
  1. 一个数异或自身奇数次还是自身，偶数次则为0

​ x ^ x = 0; x ^ 0 = x

  1. 通过异或还可以不用中间变量来交换两个整形 
1
2
3
x = x ^ y;
y = x ^ y;
x = x ^ y;
  1. 左移1在不溢出的情况下等价于乘以2

​ 右移代表整除2，不过只针对正数，如果是负数，则代表向上取整的整除2

  1. 两个质数异或值为1 代表两个数字前后最多相差1

  2. __builtin_clz(n) 计算二进制中最高位1左边0的个数（前导零的个数）

  3. __builtin_ctz(n)计算二进制中末尾0连续的个数（尾随零的个数）