位运算

zhou2023-10-192023-10-19

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

与、或和异或

注意这些运算都是建立在二进制的基础上的

and，运算符为&

1
2
3

int a=6,b=5;
cout<<(a&b)<<endl;
4

or，运算符为|

1
2
3

int a=6,b=5;
cout<<(a|b)<<endl;
7

xor，运算符为^

值得注意的是，异或的逆运算是自己的本身，所以一个数与两个相同的数进行异或运算，最后的结果是自己本身。

1
2
3

int a=6,b=5;
cout<<(a^b)<<endl;
3

num << i 表示将 num 的二进制表示向左移动 i 位所得的值。

左移n位其实也就是除以2的n次方

int num=5;
int a,b;
b = num<<2;
b = 1

num >> i 表示将 num 的二进制表示向右移动 i 位所得的值。

右移n位其实也就是乘以2的n次方

int num=5;
int a,b;
a = num>>2;
a = 20

移位运算中如果出现如下情况，则其行为未定义：

右操作数（即移位数）为负值；
右操作数大于等于左操作数的位数；

例如，对于 int 类型的变量 a ， a<<-1 和 a<<32 都是未定义的。

对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。1对一个负数执行左移操作也未定义。

对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。

取反是对一个数 num 进行的位运算，即单目运算。

取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把 num 的二进制补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）。有符号整数的符号位在 ~ 运算中同样会取反。

补码：在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

1
2
3

int num = 5,a;
a = ~num;
a = -6

注意取反不是求负数

高效地进行某些运算，代替其它低效的方式。

表示集合（常用于状压 DP）。

题目本来就要求进行位运算。

int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}
int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

1
2
3

bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

1 2	// 获取 a 的第 b 位，最低位编号为 0 int getBit(int a, int b) { return (a >> b) & 1; }

1 2	// 将 a 的第 b 位设置为 0 ，最低位编号为 0 int unsetBit(int a, int b) { return a & ~(1 << b); }

1 2	// 将 a 的第 b 位取反，最低位编号为 0 int flapBit(int a, int b) { return a ^ (1 << b); }

小技巧