文章目录
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
0001|0001=0001,0001|0000=0001,0000|0000=0000
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\&B=B\&A ,A\wedge B=B\wedge A A&B=B&A,A∧B=B∧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=A，A∣A=A零律 A & 0 = 0 A\&0=0 A&0=0互补律（注意，这不同于逻辑运算） A & ∼ A = 0 , A ∣ ∼ A = − 1 A\&\sim A=0,A|\sim A=-1 A&∼A=0,A∣∼A=−1同一律 A ∣ 0 = A ， A ∧ 0 = A A|0=A，A\wedge 0 =A A∣0=A，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−>0101 x ∣ 1 x|1 x∣1将最后一位变为 0 0 0 0101 − > 0100 0101->0100 0101−>0100，这里实际上就是先确保最低位变为 1 1 1，再减去 1 1 1。 ( x ∣ 1 ) − 1 (x|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=4 x ∣ ( 1 < < ( k − 1 ) ) x|(1<<(k-1)) x∣(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=3 x ∣ ( ( 1 < < k ) − 1 ) x|((1< x∣((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−>0111 x ∣ ( x + 1 ) x|(x+1) x∣(x+1)把右起连续的 0 0 0变为 1 1 1 1000 − > 1111 1000->1111 1000−>1111，注意是右起连续的 0 0 0 x ∣ ( x − 1 ) x|(x-1) x∣(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 那么对于负数的位运算而言，它们的操作都是建立在补码上的，得到的运算结果是补码，最后将补码结果转化成一个普通的十进制数结果。 但需要注意的是，对于有符号数的右移操作，不同的处理器架构可能有不同的规定。在某些架构中（如x86），如果对有符号数执行算术右移（arithmetic right shift），则高位空出来的位置会补上符号位；对于无符号数的右移操作，所有架构都遵循相同的规则：高位空出来的位置会补0。例如对于 − 15 -15 −15，其补码为 11110001 , 11110001, 11110001,右移一位 ( − 15 > > 1 ) (-15>>1) (−15>>1)得到的是 11111000 11111000 11111000，即 − 8 -8 −8，其他的同理。 在大多数现代处理器上，无论是有符号数还是无符号数，左移操作总是将空出来的低位补0。 这里我们介绍几个特殊的性质： 快速判断是否为 − 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，根据异或性质即可判断感谢读者 （恢。）指出错误，这里应该是要进行按位取反操作，这样如果为负数判断结果才为0 。） ，利用条件表达式就可以根据判断结果求绝对值了。如下： int abs(int a){ return ~(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 x x，转换成二进制后，是形如这样的数字： a a . . . a a 10...00 aa...aa10...00 aa...aa10...00，从右向左数有任意多个 0 0 0，直到遇见第一个 1 1 1，字母 a a a用来占位，代表 1 1 1左边的任意数字。 x − 1 x-1 x−1转换成二进制后，是形如这样的数字： a a . . . a a 01...11 aa...aa01...11 aa...aa01...11，从右向左数，原来的任意多个 0 0 0都变成 1 1 1，原来的第一个 1 1 1，变成 0 0 0，字母 a a a部分不变。对 x x x 和 x − 1 x-1 x−1 进行 按位与 计算，会得到： a a . . . a a 00...00 aa...aa00...00 aa...aa00...00，从右向左数，原来的第一个 1 1 1变成了 0 0 0，字母a部分不变。所以 x & ( x − 1 ) x \& (x-1) x&(x−1)相当于消除了 x x x 从右向左数遇到的第一个 1 1 1。那么， x x x转换成二进制后包含多少个 1 1 1，count函数里的循环就会进行多少次，直到 x x x所有的 1 1 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) { // 循环遍历从第 i 位到第 j 位 for(int pos = i; pos <= j; pos ++ ){ // 将 n 的第 pos 位设为 0 // ~(1 << pos) 创建一个在第 pos 位为 0 其他位为 1 的掩码 // 然后使用按位与运算符（&）来将 n 的第 pos 位设置为 0 n &= ~(1 << pos); } // 将 m 左移 i 位，使 m 的低位对齐到 n 的第 i 位 // 然后使用按位或运算符（|）合并 n 和 m // 这样 n 的第 i 到第 j 位就被 m 的相应位所替换 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){ // temp_a 存储 a 和 b 的按位异或结果，这相当于不带进位的加法 int temp_a = a ^ b; // temp_b 存储 a 和 b 的按位与结果并左移一位，这相当于计算进位 // 因为只有两个位都是1时才会产生进位 int temp_b = (a & b) << 1; // 更新 a 为不带进位的加法结果 a = temp_a; // 更新 b 为进位 b = temp_b; } // 当没有进位时，a 中存储了最终结果，返回 a 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) { // 检查 n 是否大于 0 // 2 的幂必须是正数，因为 0 和负数都不是 2 的幂 // 检查 n 和 n - 1 的按位与操作是否为 0 // 如果 n 是 2 的幂，则其二进制表示中只有一个 1 // 例如 2 (10), 4 (100), 8 (1000) // 当 n 是 2 的幂时，n - 1 的二进制表示是 n 的最高位 1 变为 0， // 其余位从 0 变为 1，例如 2 (10) - 1 = 1 (01), 4 (100) - 1 = 3 (011) // 因此 n & (n - 1) 将得到 0 return n > 0 && (n & (n - 1)) == 0; } };