带你走近位运算

一、位运算的规则

1.1 数字在计算机中是如何表示的？

计算机中只存在二进制，因此一个数在计算机中是以二进制的形式表示的，也被称为机器数。

机器数的分类：

原码：符号位 + 真值的绝对值
反码：正数的反码是其本身；负数的反码是在其原码的基础上，符号位不变，其余各个位取反
补码：正数的补码是其本身；负数的补码是在其反码的基础上加一

真值：带符号位的机器数对应的真正数值

⚠️注意：引入补码的目的是为了在计算机底层统一将加减法运算转化为加法运算，便于计算机的运算。

1.2 位运算规则

1.2.1 与、或、非（取反）、异或

与运算：

0 & 0 = 0;
0 & 1 = 0;
1 & 0 = 0;
1 & 1 = 1;

或运算：

0 | 0 = 0;
0 | 1 = 1;
1 | 0 = 1;
1 | 1 = 1;

异或运算：

0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

1.2.2 移位运算

左移运算：<<，将全部的二进制位向左移动若干位，高位丢弃，低位补0。对于左移运算，算术左移和逻辑左移是相同的；

右移运算：>> / >>>，将全部的二进制位向右移动若干位，低位丢弃，高位的处理取决于是算数右移还是逻辑右移，算数右移时，最高位补最高位；逻辑右移时，最高位补0

移位运算和乘除法的关系：

对于正数和 0，将一个数左移 m 位，等价于将这个数乘以2的 m 次方。将一个数右移 m 位，等价于将这个数除以2的 m次方。

1.2.3 位运算定律

幂等律：a & a = a, a | a = a
交换律：a & b = b & 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 & b) | c = (a | c) & (a | c), (a | b) & c = (a & c) | (b & c), (a ^ b) & c = (a & c) ^ (b & c)
徳摩根律：~(a & b) = (~a) | (~b), ~(a | b) = (~a) & (~b)
取反运算性质：-1 = ~0, -a = ~(a - 1)
与运算性质：a & 0 = 0, a & (-1) = a, a & (~a) = 0
或运算性质：a | 0 = a
异或运算性质：a ^ 0 = a, a ^ a = 0

1.2.4 位运算技巧

1）获取某个数第 i 位上的比特：

int getBit(int x, int i) {
    return x & (1 << i);
}

2）将某个数第 i 位置1

int setBit(int x, int i) {
    return x | (1 << i);
}

3）将某个数第 i 位置0

int clearBit(int x, int i) {
    return x & ~(1 << i);
}

4）将某个数的第 i 位设置为预设值 v

int updateBit(int x, int i, int v) {
    return (x & ~(1 << i) | (v << i));
}

二、实践高频算法题

2.1 巧用移位运算

2.1.1 位 1 的个数

191. 位1的个数 - 力扣（LeetCode）

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

分析

可以将输入的无符号整数各个 bit 位依次与 1 进行与运算，通过设置计数器统计结果，每当与运算结果为 1，计数器加一。那么，如何将各个比特位都进行运算了？可以使用移位运算来实现，比如无符号整数右移或者数值1左移。

实现

// 方法一：数值1左移
public int hammingWeight(int n) {
    int cnt = 0;
    for(int i = 0; i < 32; i++) {
        if((n & (1 << i)) != 0)
            cnt++;
    }
    return cnt;
}
// 方法二：无符号整数右移
public int hammingWeight(int n) {
	int cnt = 0;
    for(int i = 0; i < 32; i++) {
        if((n >>> i) & 1) != 0)
            cnt++;
    }
    return cnt;
}

优化

任意无符号整数 n 和 n-1 相差1，表现在比特位上相差最低位1，即n & (n-1) 的结果与 n 相差1。所以可以通过不断地执行 n &(n-1)，直至 n==0 来统计 n 中 1 的个数。

public int hammingWeight(int n) {
    int ans = 0;
    for(; n != 0; ans++) n &= (n - 1);
    return ans;
}

2.1.2 比特位计数

LCR 003. 比特位计数 - 力扣（LeetCode）

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

分析

本题可以套用上一题的逻辑，只是多了一层循环，统计结果时使用数组即可。

实现

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for(int i = 0; i <= n; i++) {
        ans[i] = countBit(i);
    }
    return ans;
}
int countBit(int x) {
    int ans = 0;
    for(; x != 0; ans++) x &= (x - 1);
    return ans;
}

2.1.3 颠倒无符号整数

190. 颠倒二进制位 - 力扣（LeetCode）

颠倒给定的 32 位无符号整数的二进制位。

分析

对于32位无符号整数，原先的第i位颠倒之后变成了31-i位，可以将无符号整数通过不断移位与 1 进行与运算，获取到当前比特位的值，再通过移位操作将当前比特位的值放置到指定的位置。

实现

public int reverseBits(int n) {
    int reversed = 0;
    int power = 31;
    while(power >= 0) {
        reversed += (n & 1) << power;
        power--;
        n >>>= 1;
    }
    return reversed;
}

2.2 位运算实现四则运算

2.2.1 位运算实现加法

371. 两整数之和 - 力扣（LeetCode）

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

分析

两个比特位相加时，不考虑溢出（进位）情况，相同为0，不同为1，这跟异或运算的性质还是一样的。进位可以通过两个比特位进行与运算判断，因为只有当两个比特位都为1时才会产生进位，此时a&b=1，进位的值时(a&b)<<1。

实现

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

2.2.2 位运算实现乘法

面试题 08.05. 递归乘法 - 力扣（LeetCode）

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

分析

不使用*运算符，可以考虑累加实现，但是题目要求需要吝啬使用，因此可以考虑使用移位运算。可以在两个加数中选择较大的作为基数，通过判断较小值对应的比特位是否为1，来判断基数是否需要累加，这样可以通过较少的加法和移位运算实现乘法。

public int multiply(int A, int B) {
    int mx = Math.max(A, B), mn = A + B - mx;
    int ans = 0;
    while(mn != 0) {
        if((mn & 1) != 0) {
            ans += mx;
        }
        mn >>>= 1;
        mx += mx;
    }
    return ans;
}