从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
一、位运算概述
我们知道，计算机中的数在内存中都是以二进制形式进行存储的 ，而位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
那么，涉及位运算的运算符如下表所示：
| 符号 | 描述 | 运算规则 |
| & | 按位与 | 两个数相应位都为1，则该位的结果为1，否则为0 |
| | | 按位或 | 两个数相应位有一个为1，则该位的结果为1，否则为0 |
| ^ | 按位异或 | 两个数相应位不同时，则该位的结果为1，否则为0 |
| ~ | 按位取反 | 对数的每一个位取反，即1变0，0变1 |
| << | 左移运算 | 将数的每个位向左移，高位丢弃，低位补0 |
| >> | 右移运算 | 将数的每个位向右移，高位补0，低位丢弃 |
位运算符举例
以a = 52和b = 1314为例
（1）按位与&：两个数相应位都为1，则该位的结果为1，否则为0
0000 0011 0100 --- 52 & 0101 0010 0010 --- 1314 ————————————————— 0000 0010 0000 --- 32
（2）按位或 | ： 两个数相应位有一个为1，则该位的结果为1，否则为0
0000 0011 0100 --- 52 | 0101 0010 0010 --- 1314 ————————————————— 0101 0011 0110 --- 1334
（3）按位异或 ^ ： 两个数相应位不同时，则该位的结果为1，否则为0
0000 0011 0100 --- 52 ^ 0101 0010 0010 --- 1314 ————————————————— 0101 0001 0110 --- 1302
（4）按位取反 ~ ： 对数的每一个位取反，即1变0，0变1（以该数存储为16位无符号整数为例）
以该数存储为16位无符号整数为例: ~ 0000 0101 0010 0010 --- 1314 —————————————————————— 1111 1010 1101 1101 --- 64221 以该数存储为16位有符号整数为例（第一位为符号位，在计算机中，负数以补码存储）: ~ 0000 0101 0010 0010 --- 1314 —————————————————————— 1111 1010 1101 1101 --- -1315
（5）左移运算 << ： 将数的每个位向左移，高位丢弃，低位补0（以该数存储为16位无符号整数为例）
<<2 0000 0101 0010 0010 --- 1314 ———————————————————————— 0001 0100 1000 1000 --- 5256
（6）右移运算 >> ： 将数的每个位向右移，高位补0，低位丢弃（以该数存储为16位无符号整数为例）
>>2 0000 0101 0010 0010 --- 1314 ———————————————————————— 0000 0001 0100 1000 --- 328
二、位运算的性质
（1）运算符的优先级
优先级需要弄清楚，如果不太清楚可以加小括号确保是想要的运算顺序，这里只是相对优先级，即只是和一些常用的算术运算符做比较。
| 优先级 | 运算符 | 结合方向 |
| 1 | −（符号运算符）,∼（取反运算符），++（自增），−−（自减） | 从右到左 |
| 2 | ∗（乘）,/（除）,%（取余） | 从左到右 |
| 3 | +（加）,−（减） | 从左到右 |
| 4 | <<（左移），>>（右移） | 从左到右 |
| 5 | >（大于）,<(小于),>=(大于等于),<=(小于等于) | 从左到右 |
| 6 | ==(等于),!=（不等于） | 从左到右 |
| 7 | &（按位与） | 从左到右 |
| 8 | ∧(按位异或) | 从左到右 |
| 9 | |(按位或) | 从左到右 |
（2）位运算符的运算律
| 公式名称 | 运算规则 |
| 交换律 | A&B=B&A，A&B=B&A，A∧B=B∧A |
| 结合律（注意结合律只能在同符号下进行） | (A&B)&C=A&(B&C)$(A |
| 等幂律 | A&A=A，A|A=A |
| 零律 | A&0=0 |
| 互补律（注意，这不同于逻辑运算） | A&∼A=0，A|∼A=−1 |
| 同一律 | A|0=A，A∧0=A |
以上仅为已证明的运算律（可能存在特殊情况和遗漏），注意：千万不要将逻辑运算的运算律或者其他的运算律与这混为一谈。
三、位运算高级操作
如下表，请读者认真阅读理解，在阅读的过程中可以对示例进行运算。
| 功能 | 示例 | 位运算 |
| 去掉最后一位 | 0100−>0010 | x>>1 |
| 在最后加一个0 | 0100−>1000 | x<<1 |
| 在最后加一个1 | 0100−>1001 | x<<1+1 |
| 将最后一位变为1 | 0100−>0101 | x|1 |
将最后一位变为0 | 0101−>0100，这里实际上就是先确保最低位变为1，再减去1。 | (x|1)-1 |
最后一位取反 | 0100−>0101 ，利用异或性质，其中除最后一位其余不变。 | x∧1 |
把右数的第k位变为1 | 0001−>1001,k=4 | x|(1<<(k-1)) |
| 把右数的第k位变为0 | 1001−>0001,k=4，这个操作实际上就是先得到了1000，然后取反得到0111，最后利用按位与的性质其余位不变，最高位为0 | x&∼(1<<(k−1)) |
| 把右数的第k位取反 | 1000−>0000,k=4，利用异或性质 | x∧(1<<(k−1)) |
| 取末k位 | 1011−>0011,k=2 | x&(1<<k−1) |
| 取右数的第k位 | 1011−>0001,k=4，右移k−1位则是去掉了最后的k−1位，我们利用按位与即可将其提取出来 | x>>(k−1)&1 |
| 把末k位全变为1 | 1000−>1111,k=3 | x|(1<<k-1) |
| 把末k位取反 | 0101−>1010,k=4 | x∧(1<<k−1) |
把右边连续的1变为0 | 0111−>0000 ，注意是右起连续的1 | x&(x+1) |
| 把右起的第一个0变为1 | 0011−>0111 | x|(x+1) |
| 把右起连续的0变为1 | 1000−>1111，注意是右起连续的0 | x|(x-1) |
| 取右边连续的1 | 1011−>0011 | (x∧(x+1))>>1 |
去掉右起的第一个1的左边 | 1101−>0001 | x&(x∧(x−1)) |
这里只是一些常用的，并不是全部，大家可以通过不断的练习，获得更多实践经验。
四、负数的位运算
首先，我们要知道，在计算机中，运算是使用的二进制补码，而正数的补码是它本身，负数的补码则是符号位不变，其余按位取反，最后再+1得到的， 例如：
15,原码:00001111补码:00001111
−15,原码:10001111补码:11110001
那么对于负数的位运算而言，它们的操作都是建立在补码上的，得到的运算结果是补码，最后将补码结果转化成一个普通的十进制数结果。但需要注意的是，符号位是需要参与运算的，而在左移右移操作中，负数右移补1，左移右边补0。例如对于-15，其补码为11110001 , 右移一位(−15>>1)得到的是11111000，即-8，其他的同理。
这里我们介绍几个特殊的性质：
（1）快速判断是否为-1
在链式前向星中，我们初始化head数组为-1，最后判断是否遍历完u的所有边时，即判断i是否为-1，我们直接用∼ i即可。原因就在于-1的补码是11111111，按位取反就变为00000000，这实际上就是0。
（2）取最低位的1，lowbit函数
也就是x\&(-x)，这在树状数组中起着巨大作用，我们来证明一下，这里取x=15，对于15\&(-15)，我们知道，在补码上进行运算得到的是00000001，需要注意二元运算的符号位我们需要进行运算。
五、位运算的一些应用
（1）位运算实现乘除法
将x左移一位实现×2，将x右移一位实现÷2。
a<<1≡a∗2
a>>1≡a/2
（2）位运算交换两整数
void swap(int &a,int &b){
a ^= b;
b ^= a;
a ^= b;
}这效率非常高，我们来剖析其原理，对于a=a∧b，则b=b∧(a∧b)，根据交换律以及异或性质，得b=b∧b∧a=0∧a=a，同理a=(a∧b)∧a=0∧b=b。这样就实现了交换操作。
（3）位运算判断奇偶数
我们知道，在二进制中，最低位决定了是奇数还是偶数，所以我们可以提取出最低位的值，即与1相与即可实现目的，为0则是偶数，为1则是奇数。
（4）位运算改变正负性和求绝对值
int change(int a){
return ~ a + 1;
}对于正数而言，补码就是原码，所以按位取反再+1则得到对应真值负数的补码，而对于负数，其补码进行按位取反再 +1则得到对应真值正数的补码，变为原码。那么知道这个我们就可以特判是否为负数==（这里通过右移31位，若为正数，则得到的是0，若为负数，则得到的是-1，而0的补码为0000，-1的补码为1111，根据异或性质即可判断。）== 再进行反转即可实现求绝对值了。如下：
int abs(int a){
return a ^ (a >> 31) ? a : ~ a + 1;
}（5）位运算实现对p取余（p为
）
int mod(int a,int p){
return a & (p - 1);
}取余实际上就是舍去大于等于p的位数，所以我们只需要保留在p范围内的数。由于我们限定了p为
，所以(p−1)一定是将小于p的最高位全部变为了1，这样再进行与操作即可得到余数。
（6）位运算统计二进制数1的个数
int count(int x){
int cnt = 0;
while(x){
x = x & (x - 1);
cnt ++;
}
return cnt;
}对于任意的x，转换成二进制后，是形如这样的数字：aa…aa10…00，从右向左数有任意多个0，直到遇见第一个1，字母a用来占位，代表1左边的任意数字。x-1转换成二进制后，是形如这样的数字：aa…aa01…11，从右向左数，原来的任意多个0都变成1，原来的第一个1，变成0，字母a部分不变。对x 和 x-1 进行 按位与 计算，会得到：aa…aa00…00，从右向左数，原来的第一个1变成了0，字母a部分不变。所以 x & (x-1)相当于消除了 x 从右向左数遇到的第一个1。那么，x转换成二进制后包含多少个1，count函数里的循环就会进行多少次，直到x所有的1都被“消除”。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程