位运算规则

通关进度

题目 说明
位运算的基本规则 通关
移位原理与乘除关系 通关
位运算的常用技巧 通关

参考资料

位运算与相关算法技巧

位运算规则

&：与运算

1
2
3
4
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

|：或运算

1
2
3
4
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

~：取反运算

1
2
~0 = 1
~1 = 0

⊕：异或运算

1
2
3
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1

<<：左移运算

将全部二进制位向左移动若干位，高位丢弃，低位补 0

>>：右移运算

将全部二进制位向右移动若干位，低位丢弃，高位的补位由算术移位或逻辑移位决定：

  • 算术右移，高位补最高位
  • 逻辑右移，高位补 0
Java 运算符 说明
<< 左移运算符，num << 1，相当于 num 乘以 2
>> 右移运算符，num >> 1，相当于 num 除以2
>>> 无符号右移，忽略符号位，空位都以 0 补齐

位运算常用技巧

位运算性质

获取

  • 用于获取整数 num 的二进制表示中指定位置 index 的位的函数
  • 通过判断运算结果是否不等于 0，即判断指定位置是否为 1
  • 如果结果为 0，表示 index 位置为 0
  • 如果结果为 1，表示 index 位置为 1
1
2
3
boolean getBit(int num, int index) {
    return ((num & (1 << index)) != 0);
}
1
2
3
4
5
6
int num = 37; // 二进制表示为 100101
int index1 = 2; // 从右往左数，第3位为1
int index2 = 4; // 从右往左数，第5位为0

boolean bit1 = getBit(num, index1);
boolean bit2 = getBit(num, index2);

设置

  • 用于将整数 num 的二进制表示中指定位置 index 的位设置为 1 的函数
1
2
3
int setBit(int num, int index) {
    return num | (1 << index);
}
1
2
3
4
int num = 37; // 二进制表示为 100101
int index = 3; // 从右往左数，第4位为0
// 输出：After setting bit at index 3 to 1: 101101
int result = setBit(num, index);

清零

  • 用于将整数 num 的二进制表示中指定位置 index 的位清零（设置为 0）的函数
1
2
3
4
int clearBit(int num, int index) {
    int mask = ~(1 << index);
    return num & mask; 
}
1
2
3
4
int num = 37; // 二进制表示为 100101
int index = 4; // 从右往左数，第5位为0
// 输出：After clearing bit at index 4: 100101
int result = clearBit(num, index);

更新

  • 用于更新整数 num 的二进制表示中指定位置 index 的位为给定值 value 的函数
1
2
3
4
int updateBit(int num, int index, int value) {
    int mask = ~(1 << index);
    return (num & mask) | (value << index);
}
1
2
3
4
5
int num = 37; // 二进制表示为 100101
int index = 2; // 从右往左数，第3位为1
int value = 0; // 更新为0
// 输出：After updating bit at index 2 to 0: 100001
int result = updateBit(num, index, value);

位运算的高频算法

位 1 的个数

191. 位1的个数

问题

【LeetCode 191】：输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数

循环检查二进制位

直接循环检查给定整数 n 的二进制位的每一位是否为 1

1
2
3
4
5
6
7
8
9
10
public int hammingWeight(int n) {
    int ret = 0;

    for (int i = 0; i < 32; i++) {
        if ((n & 1 << i) != 0) {
            ret++;
        }
    }
    return ret;
}

位运算优化

  • n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。
  • 不断让当前的 n 与 n−1 做与运算，直到 n 变为 0 即可

  • 每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数

    1
    2
    3
    4
    5
    6
    7
    8
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }

    比特位计数

    338. 比特位计数

问题

【LeetCode 338】：给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为n + 1的数组 ans 作为答案。

对从 0 到 n 的每个整数直接计算「一比特数」。每个 int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。

原始方法

1
2
3
4
5
6
7
8
9
10
11
12
// 对 0-->num 每个数计算比特数，每个 int 型数都可以用
public int[] countBits(int num) {
    int length = num + 1;
    int[] bits = new int[length];
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < 32; j++) {
            // 用于获取整数 i 二进制表示中第 j 位的值
            bits[i] += (i >> j) & 1;
        }
    }
    return bits;
}

位运算优化：n & (n-1) — 该运算将 n 的二进制表示的最后一个 1 变成 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        bits[i] = countOnes(i);
    }
    return bits;
}

public int countOnes(int x) {
    int ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}

颠倒二进制位

190. 颠倒二进制位

问题

【LeetCode 190】：颠倒给定的 32 位无符号整数的二进制位。

逐位颠倒

将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 rev 中。
每枚举一位就将 n 右移一位，这样当前 n 的最低位就是我们要枚举的比特位。当 n 为 0 时即可结束循环。

1
2
3
4
5
6
7
8
9
public int reverseBits(int n) {
    int rev = 0;
    for (int i = 0; i < 32 && n != 0; ++i) {
        rev |= (n & 1) << (31 - i);
        // 逻辑右移（无符号右移）
        n >>>= 1;
    }
    return rev;
}

位运算实现加法

371. 两整数之和

问题

【LeetCode 371】：给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

基础知识

  • 正整数的补码与原码相同；负整数的补码为其原码除符号位外的所有位取反后加 1
  • 可以将减法运算转化为补码的加法运算来实现
  • 符号位与数值位可以一起参与运算

算法思路

首先，考虑两个二进制位相加的四种情况如下：

1
2
3
4
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (进位)

可以发现，对于整数 a 和 b：

  • 在不考虑进位的情况下，其无进位加法结果为 a⊕b
  • 而所有需要进位的位为 a & b，进位后的进位结果为 (a & b) << 1

于是，可以将整数 a 和 b 的和，拆分为 a 和 b 的无进位加法结果与进位结果的和。因为每一次拆分都可以让需要进位的最低位至少左移一位，又因为 a 和 b 可以取到负数，所以我们最多需要 log⁡(max_int) 次拆分即可完成运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 *对于整数 `a` 和 `b`：
* - 在不考虑进位的情况下，其无进位加法结果为 `a⊕b`
* - 而所有需要进位的位为 `a & b`，进位后的进位结果为 `(a & b) << 1`
* 可以将整数 `a` 和 `b` 的和，拆分为 `a` 和 `b` 的无进位加法结果与进位结果的和
*/
public int getSum(int a, int b) {

    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

位运算实现乘法

面试题 08.05. 递归乘法

问题

【面试题 08.05】：递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

快速幂

其中 $b_i$ 是 0 或 1 代表整数 b 的二进制数表达中第 i 位的值

比如 13 * 12 = 13 * (8 + 4) = 13 * 8 + 13 * 4 = (13 << 3) + (13 << 2)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int multiply(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res += a;
        }
        //a左移1位
        a <<= 1;
        //b右移1位
        b >>>= 1;
    }
    return res;
}

位运算实现加减乘除

位运算实现加减乘除

位运算实现压缩存储

用 4KB 内存寻找重复元素

问题

给定一个数组，包含从 1 到 N 的整数，N 最大为 32000，数组可能还有重复值，且 N 的取值不定，若只有 4KB 的内存可用，该找出数组中所有重复元素

位运算

使用 Bitmap，对于 4kb 空间寻址范围为 $8\times{4}\times2^{10}$，完全满足题目所需。

【仅供参考】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class BitSet {

    int[] bits;

    public BitSet(int size) {
        this.bits = new int[size >> 5];
    }

    // 判断 pos 位置的数是否出现过
    boolean get(int pos) {
        // / 32
        int posBit = (pos >> 5);
        // % 32
        int bitNumber = (pos & 0x1F);
        return (bits[posBit] & (1 << bitNumber)) != 0;
    }


    // 将 pos 位置的值设置为 1
    void set(int pos) {
        // / 32
        int posBit = (pos >> 5);
        // % 32
        int bitNumber = (pos & 0x1F);
        bits[posBit] = bits[posBit] | (1 << bitNumber);
    }
    
}

public void checkDuplicatedNum(int[] number) {
    BitSet bitset = new BitSet(32000);

    for (int i = 0; i < number.length; i++) {
        int num = number[i]; // 数组范围 [1, N]
        int postion = num - 1; // num 在 bitmap 数组下标

        if (bitset.get(postion)) {
            // Visit()
            System.out.println(num);
        } else { // 第一次出现 
            bitset.set(postion);

        }
    }
}