【算法】位运算

发表于2021-11-24更新于2022-03-02字数统计4.4k阅读时长32分阅读次数

位运算

位运算技巧

位移运算：

1
2
3
4
// 有符号右移，会在最高位自动补 1
n >> 1;
// 无符号右移，最高位不会补 1
n >>> 1;

获取每个数字最右侧为 1 的位数：

1
2
3
4
// 以补码加一的形式将 n 取相反数
rightOne = n & (~n + 1);
// 等价于直接取反
rightOne = n & -n;

将二进制数字 n 最右侧的 1 变为 0，其余不变：

1
2
3
4
// 最右侧的 1 变为 0，此 1 右边的 0 都变为 1
n = n - 1;
// 最右侧的 1 变为 0
n = n & (n - 1);

统计二进制中 1 的个数：

1
2
3
4
5
6
7
8
9
10
11
public int hammingWeight(int n) {
    // 遍历 0-31 位，记录有几个 1
    int res = 0;
    while (n != 0) {
        // 累加上当前位
        res += n & 1;
        // 注意是无符号右移
        n >>>= 1;
    }
    return res;
}

判断某个数字的符号：

1
2
3
4
// 负数的最高位为 1，正数的最高位为 0
// n 先右移 31 位，得到其最高位的值，然后与 1 取异或，即可得到其符号
// 如果 n 为负数，其最高位 1 经过异或就是 0，反之就是 1
int sign = ((n >> 31) & 1) ^ 1;

判断一个 32 位正数是不是 2 的幂、4 的幂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 如果是2的幂，则其二进制位上只可能有一位为1，其他位都是0
// 例如 4：00000100  8:00001000。一次移动一位
// 这样其与自身减去一取与，得到的就是0。因为所有1都错位了
public static boolean is2Power(int n) {
    // 将最右侧的 1 变为 0
    return (n & (n - 1)) == 0;
}

// 如果是4的幂，前提得是2的幂。
// 然后找规律，4的幂的数字只可能有一位是1，并且该位肯定是在第1,2,4,6,8,10...中的某一个，其他位都为0
// 例如 16：00010000  32:0010000。一次移动两位
public static boolean is4Power(int n) {
    // 0x55555555：010101....01010101。0101四位组成一个0x5，共8个
    return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

使用位运算完成取相反数操作：

1
2
3
4
// 一个数的相反数 = 该数取补码 + 1
public static int negNum(int n) {
    return ~n + 1;
}

判断数字奇偶性：

1
2
3
x & 1;  // 因为如果 x 的最低位为1，则代表其肯定是某一个2的倍数加上了1，所以肯定是奇数
// 等价于
x % 2;

位图

位图：bit 为单位的数组。

基本数据类型数组的 bit 情况：

  • boolean[] 数组每个元素占 8 bits（1 byte = 8 bits）
  • int[] 数组每个元素占 32 bits（8 byte = 32 bits）

直接使用基本数据类型无法创建每个元素为一个bit的位图。那么我们可以考虑将基本数据类型数组拆为位图。例如可以使用 int[] 数组作为位图：

1
int[] arr = new int[10]; // 320 bits

那么如果我们想要得到第 178 个 bit 位置的数值时，我们可以：

1
2
3
4
5
6
int numIndex = 178 / 32;  // 获取第178个bit在arr[]的哪个索引位置上
int bitIndex = 178 % 32;  // 获取第178个bit在该索引位置的int数值的哪一位上（32bits中的哪一个）

// 将第bitIndex位移动到该数的最右侧（最低位），通过位移动和与1取&实现
// 注意移动的位数是32 - bitIndex，因为低位在右侧，高位在左侧，第bitIndex位想要移动到最右侧需要移动32 - bitIndex
int state = (arr[numIndex] >> (32 - bitIndex) & 1)

若想将该位的状态改为1，则可以：

1
arr[numIndex] = arr[numIndex] || (1 << (32 - bitIndex));

若想将该位的状态改为0，则可以：

1
arr[numIndex] = arr[numIndex] & (~(1 << (32 - bitIndex)));

位运算常见题目

仅使用位运算比较数字大小

给定两个有符号 32 位整数 a 和 b，不用做任何比较判断，返回 a 和 b 中较大的。

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
public static int flip(int n) {
    return n ^ 1;
}

public static int sign(int n) {
    return flip((n >> 31) & 1);
}

// 方法一：当 a 为正数，b 为负数时可能发生溢出
public static int getMax1(int a, int b) {
    int c = a - b;
    int scA = sign(c);
    int scB = flip(scA);
    return a * scA + b * scB;
}

// 方法二：不会溢出
public static int getMax2(int a, int b) {
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    int difSab = sa ^ sb;
    int sameSab = flip(difSab);
    int returnA = difSab * sa + sameSab * sc;
    int returnB = flip(returnA);
    return a * returnA + b * returnB;
}

public static void main(String[] args) {
    int a = -16;
    int b = 1;
    System.out.println(getMax1(a, b));
    System.out.println(getMax2(a, b));
    a = 2147483647;
    b = -2147480000;
    System.out.println(getMax1(a, b)); // wrong answer because of overflow
    System.out.println(getMax2(a, b));

}

仅使用位运算实现加减乘除

https://www.bilibili.com/video/BV13g41157hK?p=15

给定两个有符号 32 位整数 a 和 b，不能使用算术运算符，分别实现 a 和 b 的加、减、乘、除运算。

加法

  • 异或运算 ^ （a ^ b）：两个数无进位相加的结果
  • 与运算 & 后再左移一位（(a & b) << 1）：两个数的进位结果

使用这两个运算即可实现加法：进位相加结果加上进位结果就是二者的和，因此可以一直重复该过程直到进位结果为 0。具体做法是一直计算 a ^ b 和 (a & b) << 1，直到 (a & b) << 1 == 0，说明不再有进位信息了，则两个数的相加结果就是此时的 a ^ b。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int add(int a, int b) {
    int sum = a;
    // 当 b == 0 时，代表此时的无进位相加结果就是最终结果（因为没进位了）
    while (b != 0) {
        // 无进位相加结果
        sum = a ^ b;
        // a + b 的结果等于 (a ^ b) + ((a & b) << 1)
        // 那么就更新计算目标，使得 a =  (a ^ b)，b = (a & b) << 1
        
        // 更新 b 为进位结果
        b = (a & b) << 1;
        // 更新 a 为二者无进位相加结果
        a = sum;
    }
    return sum;
}

减法

a - b 可以转换为 a + (-b)。因此取 b 的相反数后即可使用加法运算得到 a - b 的结果。

1
2
3
4
5
6
7
8
9
// 一个数的相反数 = 该数取补码 + 1
public static int negNum(int n) {
    return add(~n, 1);
}

// 减法
public static int minus(int a, int b) {
    return add(a, negNum(b));
}

乘法

二进制进行乘法 a * b 时，每次判断当前的 b 的最右位是否为 1，若是则对 a 左移一位后累加到当前结果中，然后 b 右移一位，继续判断当前 b 的最右位是否为 1，若不是则不累加当前结果，仍然左移 a，右移 b。重复该过程直至 b == 0。

image-20211207154803047 
1
2
3
4
5
6
7
8
9
10
11
public static int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return res;
}

除法

二进制的除法其实就是乘法的逆序。先将 b 左移到最左侧的比 a 小的位置，在该位置记1，代表 a / b 的最大值在该位置；然后 b 左移到最左侧的右侧某一个比 a 小的位置，再将该位置记1，代表 a / b 的第二大位置在该位置……重复该过程直到 b 不能在往左侧移动，即完成了除法。

注意：在实现时因为 b 左移可能会溢出，因此改用 a 右移到最左侧比 b 的位置，来取代 b 左移。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 一个数的相反数 = 该数取补码 + 1
public static int negNum(int n) {
    return add(~n, 1);
}

public static boolean isNeg(int n) {
    return n < 0;
}

public static int div(int a, int b) {
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    for (int i = 31; i > -1; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}

public static int divide(int a, int b) {
    if (b == 0) {
        throw new RuntimeException("divisor is 0");
    }
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        return 1;
    } else if (b == Integer.MIN_VALUE) {
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        int res = div(add(a, 1), b);
        return add(res, div(minus(a, multi(res, b)), b));
    } else {
        return div(a, b);
    }
}

// 测试
public static void main(String[] args) {
    int a = (int) (Math.random() * 100000) - 50000;
    int b = (int) (Math.random() * 100000) - 50000;
    System.out.println("a = " + a + ", b = " + b);
    System.out.println(add(a, b));
    System.out.println(a + b);
    System.out.println("=========");
    System.out.println(minus(a, b));
    System.out.println(a - b);
    System.out.println("=========");
    System.out.println(multi(a, b));
    System.out.println(a * b);
    System.out.println("=========");
    System.out.println(divide(a, b));
    System.out.println(a / b);
    System.out.println("=========");

    a = Integer.MIN_VALUE;
    b = 32;
    System.out.println(divide(a, b));
    System.out.println(a / b);
}

Pow(a, b)

方法一：递归

image-20211214211359973

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

方法二：位运算技巧

image-20211214211721186

image-20211214211931855

将幂的大小进行二进制拆分，将二进制位为1的组分进行相乘即可得到的答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public double myPow(double x, int n) {
        // 记得先转换成long，防止n转换成相反数时溢出。例如n取最小的负数时，其相反数会溢出
        long N = n;
        return N >= 0 ? quickMulti(x, N) : quickMulti(1.0 / x, -N);
    }

    public double quickMulti(double x, long n) {
        double res = 1.0;
        // 当前的累积：x^1 * x^2 * x^4 * x^8 ...
        // 每次 tmp 变为 tmp * tmp，代表不断向高位移动
        double tmp = x;
        // n 每次右移一位，判断当前最低位是否是1，如果是则累乘上res，否则不乘
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                res *= tmp;
            }
            // tmp 不断向高位移动
            tmp *= tmp;
        }
        return res;
    }
}

数组中数字出现的次数

剑指 Offer 56 - II. 数组中数字出现的次数 II：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

方法一：哈希表记录

最简单的方式就是使用哈希表记录每个数字出现的频次，最后选出只有一次的。该方法空间复杂度较高。

方法二：遍历统计

思路：遍历一遍数组，统计每个数字的 32 位二进制数字出现的频次，存放在数组中，最后遍历 32 位的每一位，计算当前位为 1 的数量，对 3 取余，那么最后剩下的数字就是只出现过一次的数字，那些出现 3 次的数字对 3 取余后为 0。需要特别注意位数组的顺序。

Picture1.png

代码：

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
public int singleNumber(int[] nums) {
    // 遍历一遍数组，统计每个数字的32位二进制数字，存放在数组中，最后遍历32位的每一位，计算当前位为1的数量，对3取余
    int[] count = new int[32];
    for (int num : nums) {
        for (int i = 31; i >= 0; i--) {
            // 从低位向高位遍历，将当前位的数字存放到count对应位置中，然后num无符号右移，代表将比较新的低位
            // 注意每次比较的都是当前num的最低位，所以count中保存的顺序是：从高位到低位
            count[i] += num & 1;
            num >>>= 1;
        }
    }

    // 全部加入到count数组后，开始遍历每一位，计算所有位上数量和对m取余的结果，将其拼接起来就是那个只出现过一次的数字
    int res = 0;
    for (int i = 0; i < 32; i++) {
        // res就是目标数字在当前位的二进制值
        // 因为res左移后新出现的低位为0，所以要用或运算
        // % 3 的结果要么是0要么是1
        res |= count[i] % 3;
        // 除了最低位以外，每次取得当前位的值后都要左移以将当前为移动到应该在的地方
        // 但是注意在最低位时不能再移动了，否则就会多移动一次，因为i=31处理完后没有下一位需要判断了，也就不需要移动了
        // 或者将左移放到 res |= 的上一行，也能表示最后一位处理完不再左移
        if (i != 31) {
            res <<= 1;
        }
    }
    return res;
}

方法三：有限状态机（最佳）

使用有限状态机来统计每个数字的每一位出现的次数，但不通过数组保存的方式，而是通过有限状态机来进行统计：

对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0, 1, 2。

  • 若输入二进制位 1 ，则状态按照以下顺序转换；
  • 若输入二进制位 0 ，则状态不变。
Picture2.png

如下图所示，由于二进制只能表示 0, 1，因此需要使用两个二进制位来表示 3 个状态。设此两位分别为 two, one，则状态转换变为：00 → 01 → 10 → 00 → ⋯

Picture3.png

接下来，需要通过 状态转换表 导出 状态转换的计算公式 。

计算 one 方法：

设当前状态为 two one，此时输入二进制位 n 。如下图所示，通过对状态表的情况拆分，可推出 one 的计算方法为：

1
2
3
4
5
6
7
if two == 0:
  if n == 0:
    one = one
  if n == 1:
    one = ~one
if two == 1:
    one = 0

引入 异或运算 ，可将以上拆分简化为：

1
2
3
4
if two == 0:
    one = one ^ n
if two == 1:
    one = 0

引入 与运算 ，可继续简化为：

1
one = one ^ n & ~two

Picture4.png

计算 two 方法：

由于是先计算 one，因此应在新 one 的基础上计算 two 。如下图所示，修改为新 one 后，得到了新的状态图。观察发现，可以使用同样的方法计算 two ，即：

1
two = two ^ n & ~one

Picture5.png

以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。

遍历完所有数字后，各二进制位都处于状态 00 和状态 01 （取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 twos 恒为 00 ），因此返回 ones 即可。

详细解释见：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/ji-yu-krahetsda-lao-gei-chu-de-you-xian-67dkc/

代码：

1
2
3
4
5
6
7
8
9
10
11
public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for(int num : nums){
        // 同时计算出32位上新的状态情况
        // 记住规律背下来
        ones = ones ^ num & ~twos;
        twos = twos ^ num & ~ones;
    }
    // 全部算完后，twos肯定都是0，因为只有一个数只出现过一次，所以某一位不可能有2个，只可能是0或1，也就只在ones上
    return ones;
}

异或操作题目

出现奇数次的数字

题目：一个数组中，除了一个数字出现奇数次，其他数字都出现偶数次，找出这个数字。

思路：可以使用异或操作实现。异或操作的性质：

  • a^a=0；自己和自己异或等于0
  • a^0=a；任何数字和0异或还等于他自己
  • abc=acb；异或运算具有交换律

所以将整个数组进行异或，偶数次的数字和自己异或的结果为0，因此最后得到的结果就是那个出现奇数次的数字。

示意图：

image-20211218194147466

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package com.zhao;

public class Eor {

    // 适用题目: 除了一个数字存在奇数次, 其他数字都存在偶数次
    public static int singleNumber(int[] nums) {
        int eor = 0;
        for (int i = 0; i < nums.length; i++) {
            eor = eor ^ nums[i];
        }
        // 连续异或得到的结果就是那个唯一出现奇数次的数字
        return eor;
    }
}

出现偶数次的数字

剑指 Offer 56 - I. 数组中数字出现的次数：一个数组中，除了两个数字出现奇数次，其他数字都出现偶数次，找出这两个数字。

思路：可以使用异或操作实现，但需要一些技巧：

  • 首先将0与整个数组的元素进行异或，得到的结果为那两个出现奇数次的数字的异或： eor = a ^ b
  • 接着分析 eor 的特性：其不等于0，说明其8个bit上必定有某一位为1，那么就找出这一位。这里使用技巧找出 eor 最右侧的为1的位数：rightOne = eor & (~eor + 1)
  • 得到 rightOne 后，将整个数组里的元素分为两类：
    • rightOne 位上为1的元素
    • rightOne 位上不为1的元素
  • 只对其中的某一类元素进行累计求异或操作，得到的结果 onlyOneEor 就是a或b其中的某一个
  • 接着计算 onlyOneEor ^ eor 即可得到a或b中的另一个。
  • 至此找出了两个数字

示意图：

image-20211218194213340

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 适用题目: 除了两个数字存在奇数次, 其他数字都存在偶数次
public static void twoSingleNumber(int[] nums) {
    int eor = 0;
    for (int n : nums) {
        eor = eor ^ n;
    }

    // 连续异或结果就是那两个出现奇数次的数字a和b的异或 a ^ b
    // eor != 0: 说明eor的8个位上必有一个为1, 且a和b在这一位上一个为1一个为0
    int rightOne = eor & (~eor + 1); // 将eor最右侧位的1找出来

    // 只将数组中最右侧位也为1的数字找出来, 目的是将a和b区分出来,因为二者只有一个这一位为1

    int onlyOneEor = 0;
    for (int n : nums) {
        if ((n & rightOne) != 0)
            onlyOneEor ^= n;
    }

    System.out.println(eor);
    System.out.println((eor ^ onlyOneEor));
}