跳转至

位运算总结（转载）

（转载自 位运算全面总结，关于位运算看这篇就够了）

文章目录

  • 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<<k=0100，k=2 0001<<k=0100，k=2， 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−>0010x > > 1 x>>1 x>>1
在最后加一个 0 0 00100 − > 1000 0100->1000 0100−>1000x < < 1 x<<1 x<<1
在最后加一个 10100 − > 1001 0100->1001 0100−>1001( x < <1) + 1 (x<<1)+1 (x<<1)+1
将最后一位变为 1 1 10100 − > 0101 0100->0101 0100−>0101x ∣ 1 x|1 x∣1
将最后一位变为 0 0 00101 − > 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 10001 − > 1001 , k = 4 0001->1001,k=4 0001−>1001,k=4x ∣ ( 1 < < ( k − 1 ) ) x|(1<<(k-1)) x∣(1<<(k−1))
把右数的第 k k k 位变为 0 0 01001 − > 0001 , k = 4 1001->0001,k=4 1001−>0001,k=4，这个操作实际上就是先得到了 1000 1000 1000，然后取反得到 0111 0111 0111，最后利用按位与的性质其余位不变，最高位为 0 0 0x & ( ∼ ( 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=2x & ( ( 1 < <k) − 1 ) x\&((1<<k)-1) x&((1<<k)−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 11000 − > 1111 , k = 3 1000->1111,k=3 1000−>1111,k=3x ∣ ( ( 1 < <k) − 1 ) x|((1<<k)-1) x∣((1<<k)−1)
把末 k k k 位取反0101 − > 1010 , k = 4 0101->1010,k=4 0101−>1010,k=4x ∧ ( ( 1 < <k) − 1 ) x\wedge ((1<<k)-1) x∧((1<<k)−1)
把右边连续的 1 1 1 变为 0 0 00111 − > 0000 0111->0000 0111−>0000 ，注意是右起连续的 1 1 1x & ( x + 1 ) x\&(x+1) x&(x+1)
把右起的第一个 0 0 0 变为 1 1 10011 − > 0111 0011->0111 0011−>0111x ∣ ( x + 1 ) x|(x+1) x∣(x+1)
把右起连续的 0 0 0 变为 1 1 11000 − > 1111 1000->1111 1000−>1111，注意是右起连续的 0 0 0x ∣ ( x − 1 ) x|(x-1) x∣(x−1)
取右边连续的 1 1 11011 − > 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−>0001x & ( 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

  • 位运算交换两整数

Text Only
1
2
3
4
5
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 则是奇数。

  • 位运算改变正负性和求绝对值

Text Only
1
2
3
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
。） ，利用条件表达式就可以根据判断结果求绝对值了。如下：

Text Only
1
2
3
int abs(int a){
    return ~(a >> 31) ? a : ~a + 1;
}
  • 位运算实现对 p p p 取余（p 为 2 k 2^k 2k）
Text Only
1
2
3
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 的个数
Text Only
1
2
3
4
5
6
7
8
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 位的子串）

    样例：

    Text Only
    1
2
3
4
    输入: 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 代码

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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）的形式返回。不能使用 + 等数学运算符。

    样例：

    输入：

    Text Only
    1
2
    a = 1
b = 2

    输出：

    输入：

    Text Only
    1
2
    a = -1
b = 1

    输出：

  • 解题思路

    这题我们可以利用异或操作来实现，因为异或操作有一个别名叫不进位加法。那么进位操作我们实际上就可以通过 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 代码

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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 代码

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};