文章目录
位运算详解1、位运算概述2、位运算的性质2.1、运算符的优先级2.2、位运算符的运算律
3、位运算高级操作4、负数的位运算5、位运算的一些应用6、位运算例题6.1、更新二进制位6.2、A+B问题6.3、O(1)时间检测2的幂次
位运算详解
1、位运算概述
我们知道，计算机中的数在内存中都是以二进制形式进行存储的 ，而位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
那么，涉及位运算的运算符如下表所示：
符号描述运算规则实例（以四位二进制数为例）&与两个位都为1时，结果才为1。
0001
&
0001
=
1
,
0001
&
0000
=
0
,
0000
&
0000
=
0000
0001\&0001=1,0001\&0000=0,0000\&0000=0000
0001&0001=1,0001&0000=0,0000&0000=0000|或两个位都为0时，结果才为0。0001|0001=0001,0001|0000=0001,0000|0000=0000^异或两个位相同为0，相异为1。
0001
∧
0001
=
0000
,
0001
∧
0000
=
1
,
0000
∧
0000
=
0
0001 \wedge0001=0000,0001\wedge0000=1,0000\wedge 0000=0
0001∧0001=0000,0001∧0000=1,0000∧0000=0~取反0变1，1变0。
∼
0
=
1
,
∼
1
=
0
\sim0=1,\sim 1 = 0
∼0=1,∼1=0<<左移各二进位全部左移若干位，高位丢弃，低位补0。
0001
<
<
k
=
0100
，
k
=
2
0001< 0001< k k k是左移的位数，这里 k = 2 k=2 k=2>>右移各二进位全部右移若干位，对无符号数，高位补0，有符号数，右移补 1 1 1。 0100 > > k = 0001 ， k = 2 0100>>k=0001，k=2 0100>>k=0001，k=2， k k k是右移的位数，这里 k = 2 k=2 k=2 看完，你可能会觉得挺简单的，但位运算的难点并不在这，而在于其性质、高级操作和它的应用。、 2、位运算的性质 2.1、运算符的优先级 优先级需要弄清楚，如果不太清楚可以加小括号确保是想要的运算顺序，这里只是相对优先级，即只是和一些常用的算术运算符做比较。 优先级运算符结合方向1 − （ 符 号 运 算 符 ） , ∼ （ 取 反 运 算 符 ） ， + + （ 自 增 ） ， − − （ 自 减 ） -（符号运算符）,\sim（取反运算符）， ++（自增），--（自减） −（符号运算符）,∼（取反运算符），++（自增），−−（自减）从右到左2 ∗ （ 乘 ） , / （ 除 ） , % （ 取 余 ） *（乘）,/（除）,\%（取余） ∗（乘）,/（除）,%（取余）从左到右3 + （ 加 ） , − （ 减 ） +（加）,-（减） +（加）,−（减）从左到右4 < < （ 左 移 ） ， > > （ 右 移 ） <<（左移），>>（右移） <<（左移），>>（右移）从左到右5 > （ 大 于 ） , < ( 小 于 ) , > = ( 大 于 等 于 ) , < = ( 小 于 等 于 ) >（大于）,<(小于),>=(大于等于),<=(小于等于) >（大于）,<(小于),>=(大于等于),<=(小于等于)从左到右6 = = ( 等 于 ) , ! = （ 不 等 于 ） ==(等于),!=（不等于） ==(等于),!=（不等于）从左到右7 & （ 按 位 与 ） \&（按位与） &（按位与）从左到右8 ∧ ( 按 位 异 或 ) \wedge (按位异或) ∧(按位异或)从左到右9|(按位或)从左到右 2.2、位运算符的运算律 公式名称运算规则交换律A&B=B&A ,A&B=B&A,A ∧ \wedge ∧ B=B ∧ \wedge ∧ A结合律（注意结合律只能在同符号下进行） ( A & B ) & C = A & ( B & C ) (A\&B)\&C=A\&(B\&C) (A&B)&C=A&(B&C)$(A等幂律 A & A = A A\&A=A A&A=A，A|A=A零律A|1=1，A&0=0互补律（注意，这不同于逻辑运算） A & ∼ A = 0 A\&\sim A=0 A&∼A=0,A| ∼ A = − 1 \sim A=-1 ∼A=−1同一律A|0=A，A ∧ 0 = A \wedge 0 =A ∧0=A 以上仅为已证明的运算律（可能存在遗漏），其余的博主均认为是不符合不成立的，注意：千万不要将逻辑运算的运算律或者其他的运算律与这混为一谈。 3、位运算高级操作 如下表，请读者认真阅读理解，在阅读的过程中可以对示例进行运算。 功能示例位运算去掉最后一位 0100 − > 0010 0100->0010 0100−>0010 x > > 1 x>>1 x>>1在最后加一个 0 0 0 0100 − > 1000 0100->1000 0100−>1000 x < < 1 x<<1 x<<1在最后加一个1 0100 − > 1001 0100->1001 0100−>1001 x < < 1 + 1 x<<1+1 x<<1+1将最后一位变为 1 1 1 0100 − > 0101 0100->0101 0100−>0101x|1将最后一位变为 0 0 0 0101 − > 0100 0101->0100 0101−>0100，这里实际上就是先确保最低位变为 1 1 1，再减去 1 1 1。x|1-1最后一位取反 0100 − > 0101 0100->0101 0100−>0101 ，利用异或性质，其中除最后一位其余不变。 x ∧ 1 x\wedge1 x∧1把右数的第 k k k位变为 1 1 1 0001 − > 1001 , k = 4 0001->1001,k=4 0001−>1001,k=4x|(1<<(k-1))把右数的第 k k k位变为 0 0 0 1001 − > 0001 , k = 4 1001->0001,k=4 1001−>0001,k=4，这个操作实际上就是先得到了 1000 1000 1000，然后取反得到 0111 0111 0111，最后利用按位与的性质其余位不变，最高位为 0 0 0 x & ∼ ( 1 < < ( k − 1 ) ) x\&\sim(1<<(k-1)) x&∼(1<<(k−1))把右数的第 k k k位取反 1000 − > 0000 , k = 4 1000->0000,k=4 1000−>0000,k=4，利用异或性质 x ∧ ( 1 < < ( k − 1 ) ) x\wedge (1<<(k-1)) x∧(1<<(k−1)) 由于表长限制，这里接下表继续： 功能示例位运算取末 k k k位 1011 − > 0011 , k = 2 1011->0011,k=2 1011−>0011,k=2 x & ( 1 < < k − 1 ) x\&(1< x&(1< k k k位 1011 − > 0001 , k = 4 1011->0001,k=4 1011−>0001,k=4，右移 k − 1 k-1 k−1位则是去掉了最后的 k − 1 k-1 k−1位，我们利用按位与即可将其提取出来 x > > ( k − 1 ) & 1 x>>(k-1)\&1 x>>(k−1)&1把末 k k k位全变为 1 1 1 1000 − > 1111 , k = 3 1000->1111,k=3 1000−>1111,k=3x|(1< k k k位取反 0101 − > 1010 , k = 4 0101->1010,k=4 0101−>1010,k=4 x ∧ ( 1 < < k − 1 ) x\wedge (1< x∧(1< 1 1 1变为 0 0 0 0111 − > 0000 0111->0000 0111−>0000 ，注意是右起连续的 1 1 1 x & ( x + 1 ) x\&(x+1) x&(x+1)把右起的第一个 0 0 0变为 1 1 1 0011 − > 0111 0011->0111 0011−>0111x|(x+1)把右起连续的 0 0 0变为 1 1 1 1000 − > 1111 1000->1111 1000−>1111，注意是右起连续的 0 0 0x|(x-1)取右边连续的 1 1 1 1011 − > 0011 1011->0011 1011−>0011 ( x ∧ ( x + 1 ) ) > > 1 (x\wedge (x+1))>>1 (x∧(x+1))>>1去掉右起的第一个 1 1 1的左边 1101 − > 0001 1101->0001 1101−>0001 x & ( x ∧ ( x − 1 ) ) x\&(x\wedge (x-1)) x&(x∧(x−1)) 当然，这里只是一些常用的，并不是全部，位运算的神奇远不止于此。 4、负数的位运算 首先，我们要知道，在计算机中，运算是使用的二进制补码，而正数的补码是它本身，负数的补码则是符号位不变，其余按位取反，最后再 + 1 +1 +1得到的， 例如： 15 15 15,原码: 00001111 00001111\space 00001111 补码: 00001111 00001111 00001111 − 15 -15 −15,原码: 10001111 10001111\space 10001111 补码: 11110001 11110001 11110001 那么对于负数的位运算而言，它们的操作都是建立在补码上的，得到的运算结果是补码，最后将补码结果转化成一个普通的十进制数结果。但需要注意的是，符号位是需要参与运算的，而在左移右移操作中，负数右移补 1 1 1，左移右边补 0 0 0。例如对于 − 15 -15 −15，其补码为 11110001 , 11110001, 11110001,右移一位 ( − 15 > > 1 ) (-15>>1) (−15>>1)得到的是 11111000 11111000 11111000，即 − 8 -8 −8，其他的同理。 这里我们介绍几个特殊的性质： 快速判断是否为 − 1 -1 −1 在链式前向星中，我们初始化 h e a d head head数组为 − 1 -1 −1，最后判断是否遍历完 u u u的所有边时，即判断 i i i是否为 − 1 -1 −1，我们直接用 ∼ i \sim i ∼i即可。原因就在于 − 1 -1 −1的补码是 11111111 11111111 11111111，按位取反就变为 00000000 00000000 00000000，这实际上就是 0 0 0。 取最低位的 1 1 1，lowbit函数 也就是 x & ( − x ) x\&(-x) x&(−x)，这在树状数组中起着巨大作用，这里指路一篇树状数组讲解 b l o g blog blog:点这里，我们来证明一下，这里取 x = 15 x=15 x=15，对于 15 & ( − 15 ) 15\&(-15) 15&(−15)，我们知道，在补码上进行运算得到的是 00000001 00000001 00000001，需要注意二元运算的符号位我们需要进行运算。 5、位运算的一些应用 位运算实现乘除法 将 x x x左移一位实现 × 2 \times 2 ×2，将 x x x右移一位实现 ÷ 2 \div2 ÷2。 a < < 1 ≡ a ∗ 2 a<<1 \equiv a*2 a<<1≡a∗2 a > > 1 ≡ a / 2 a >>1 \equiv a/2 a>>1≡a/2 位运算交换两整数 void swap(int &a,int &b){ a ^= b; b ^= a; a ^= b; } 这效率非常高，我们来剖析其原理，对于 a = a ∧ b a=a\wedge b a=a∧b，则 b = b ∧ ( a ∧ b ) b = b\wedge(a\wedge b) b=b∧(a∧b)，根据交换律以及异或性质，得 b = b ∧ b ∧ a = 0 ∧ a = a b=b\wedge b\wedge a=0\wedge a=a b=b∧b∧a=0∧a=a，同理 a = ( a ∧ b ) ∧ a = 0 ∧ b = b a=(a\wedge b)\wedge a=0\wedge b=b a=(a∧b)∧a=0∧b=b。这样就实现了交换操作。 位运算判断奇偶数 我们知道，在二进制中，最低位决定了是奇数还是偶数，所以我们可以提取出最低位的值，即与 1 1 1相与即可实现目的，为 0 0 0则是偶数，为 1 1 1则是奇数。 位运算改变正负性和求绝对值 int change(int a){ return ~ a + 1; } 对于正数而言，补码就是原码，所以按位取反再 + 1 +1 +1则得到对应真值负数的补码，而对于负数，其补码进行按位取反再 + 1 +1 +1则得到对应真值正数的补码，变为原码。那么知道这个我们就可以特判是否为负数==（这里通过右移 31 31 31位，若为正数，则得到的是 0 0 0，若为负数，则得到的是 − 1 -1 −1，而 0 0 0的补码为 0000 0000 0000, − 1 -1 −1的补码为 1111 1111 1111，根据异或性质即可判断。）== 再进行反转即可实现求绝对值了。如下： int abs(int a){ return a ^ (a >> 31) ? a : ~ a + 1; } 位运算实现对 p p p取余（p为 2 k 2^k 2k） int mod(int a,int p){ return a & (p - 1); } 取余实际上就是舍去大于等于 p p p的位数，所以我们只需要保留在 p p p范围内的数。由于我们限定了 p p p为 2 k 2^k 2k，所以 ( p − 1 ) (p - 1) (p−1)一定是将小于 p p p的最高位全部变为了 1 1 1，这样再进行与操作即可得到余数。 位运算统计二进制数 1 1 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都被“消除”。 6、位运算例题 6.1、更新二进制位 题面 给出两个32位的整数N和M，以及两个二进制位的位置i和j。写一个方法来使得N中的第i到j位等于M（M会是N中从第i为开始到第j位的子串） 样例： 输入: N=(10000000000)2 M=(10101)2 i=2 j=6 输出: N=(10001010100)2 输入: N=(10000000000)2 M=(11111)2 i=2 j=6 输出: N=(10001111100)2 解题思路 结合所学，我们的思路应该就是先将第 i i i位到第 j j j位全部变为 0 0 0，再将与左移 i i i位的 M M M进行或操作。 AC代码 class Solution { public: int updateBits(int n, int m, int i, int j) { for(int pos = i; pos <= j; pos ++ ){ n &= ~(1 << pos); } return n | (m << i); } }; 6.2、A+B问题 题面 给出两个整数 a 和 b , 求他们的和并以整数（int）的形式返回。不能使用 + 等数学运算符。 样例： 输入： a = 1 b = 2 输出： 3 输入： a = -1 b = 1 输出： 0 解题思路 这题我们可以利用异或操作来实现，因为异或操作有一个别名叫不进位加法。那么进位操作我们实际上就可以通过 a & b a\&b a&b来实现，因为 a & b a\&b a&b得到的都是 a a a和 b b b上都有的 1 1 1，我们再左移即得到的是进位之后的结果，所以 a + b = ( a ∧ b ) + ( a & b < < 1 ) a+b=(a\wedge b)+(a\&b<<1) a+b=(a∧b)+(a&b<<1)。通过这样模拟竖式加法操作即可。 AC代码 class Solution { public: int aplusb(int a, int b) { while(b != 0){ int temp_a = a ^ b; int temp_b = (a & b) << 1; a = temp_a; b = temp_b; } return a; } }; 6.3、O(1)时间检测2的幂次 题面 用 O(1) 时间检测整数 n 是否是 2 的幂次。 样例 n=4，返回 true; n=5，返回 false. 挑战 O(1) 时间复杂度 解题思路 首先我们知道 2 k 2^k 2k是大于 0 0 0的，这里我们需要特判，同理， 2 k 2^k 2k的二进制表示中只有 1 1 1个 1 1 1，故我们可以利用 x & ( x − 1 ) x\&(x-1) x&(x−1)来消除唯一的 1 1 1判断是否等于 0 0 0即可。 AC代码 class Solution { public: bool checkPowerOf2(int n) { // write your code here return n > 0 && (n & (n - 1)) == 0; } };