Bit operation

基本运算

1.& 运算符

与运算符，两位都为1时，结果为1，否则为0。

2.| 运算符

或运算符，两位都为0时，结果为0，否则为1。

3.^ 运算符

异或运算符，两位相同时为1，不同为0。

4.~ 运算符

取反运算符，按位取反。

5.<< 左移运算符

向左移动x位，数值大小变为原来的2x倍

取模，例如int型整数有32位，至多移32位，对于1<<35,1<<3结果是相同的。

6.>> 右移运算符

向右移动x位，数值大小缩小为原来的2x倍，由逻辑右移和算数右移两种，在C++中取决于数据类型

运算定律

• 交换律始终成立

• 结合律只对单一运算成立

• & |是不可逆运算，造成信息丢失，仅仅构成交换幺半群

• ^ 符合结合律，^0不变，也就是说，^ 运算在S = {0, 1}下构成一个幺半群，其单位元为0，且任意元素的可逆元素为自身，则构成了一个群，另外，由于位运算交换律始终成立，这个群又是一个阿贝尔群（交换群）。

• 证明如下
  $
  我们说(S, *)是一个幺半群,该二元运算满足结合律，且具有单位元，即
  $
  $$
  (1)\forall x, y, z \in S, x * (y * z) = (x * y) * z
  $$
  $$
  (2)\exists 0 \in S, \forall x \in S, 0 * x = x * 0 = x
  $$
  $
  因为(S, *)是一个幺半群，且S中所有元素可逆，我们说(S, *)是一个群，即
  $
  $$
  \forall x \in G, \exists y \in G, x * y = y * x = 0
  $$
  $
  由于位运算符合交换律，(S, *)又是一个阿贝尔群
  $

• 这个证明可以推广到任意位的二进制数上，单位元仍是0b0,逆元仍是元素本身

常用操作

• & | ^ 对bit的影响

  • &0变0
  • &1不变
  • |0不变
  • |1变1
  • ^0不变
  • ^1位取反

example

0 & 0 -> 0
1 & 0 -> 0

0 & 1 -> 0
1 & 1 -> 1

0 | 0 -> 0
1 | 0 -> 1

0 | 1 -> 1
1 | 1 -> 1

0 ^ 0 -> 0
1 ^ 0 -> 1

0 ^ 1 -> 1
1 ^ 1 -> 0

• 二进制补码相反数

example

int negate(int x) {
    return (~x) + 1;
}
// 取反再加一
int x = 0x1;  // x == 1
int y = ~x + 1;   // y == 0x1111...1110 + 1 == -1

• 交换两个整数值 / 交换且保证两个数的二进制位模式不变

example

int swap(int &a,int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

• 判断奇偶

example

if((a & 1) == 0){
  //是个偶数
}
else
  //是个奇数

奇技淫巧？

• 位运算实现x ? y : z

example

int conditional(int x, int y, int z) {
    x = !!x;
    return (~x + 1) & y | ~(~x + 1) & z;
}