位运算

发表于 更新于 分类于 ， Valine：

对于编程语言，位运算更加接近计算机底层，在可以使用位运算的时候使用位运算，可以提升程序的运行效率。

1. 基础知识

Java 中有如下位运算符(Ref)：

  • 位与：&
  • 位或：| （inclusive OR）
  • 位异或（XOR）：^ （exclusive OR）
  • 位取反：~
  • 带符号移位，符号位不变，高位（低位）补零：>>(右移)；<<(左移)；
  • 无符号移位，高位补零，符号位也移动（只有无符号右移，没有无符号左移！！）：>>>(右移)；

一些例子：

1
2
3
4
5
6
7
8
9
int a = 5, b = 7;
int c1 = a&b; // 5
int c2 = a|b; // 7
int c3 = a^b; // 2
int c4 = ~a; // -6 !! 负数的绝对值 = 除符号位外取反加一
a = 10;
int c5 = a >>> 1;   // 5， 与 a >> 1 的结果相同
a = 10;
int c6 = a >>> 1;   // 2147483643, 符号位不保留

2. 例子

2.1. 二进制中1的个数

LeetCode题目

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

该题欲找出二进制串中1的个数，可以使用按位右移的方法，逐个的将 1 移动到最低位，直到当前数字变为零为止。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res += n & 1;
            n = n >>> 1;
        }
        return res;
    }
}

参考题解，这一题还有更优化的解法。

因为 n & (n - 1) 的效果是消去 n 的最低位的1, 例如 n = 12, 对应2进制为 0000,1100(以8位为例子)， n - 1 的二进制表达为：0000,1011, 可以看到，效果是将原数中最低位的 1 变为 0， 然后更低位全部变为 1。故 n & (n - 1) 的效果是将n 中最低位的 1 变为 0，其余位不变。

根据上述分析，有如下实现：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            n = n & (n-1);
            res ++;
        }
        return res;
    }
}

2.2 数值的整数次方

LeetCode题目-数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

对于这道题来说，位移运算是一个小的技巧补充 - 用于实现快速的除2 计算。

这道题的核心难点其实比较像前面总结过的大数越界问题中，使用快速求幂法 的那道题目。具体的，是通过将指数不断的除2，来快速求解答案。求解过程中，需要分奇偶讨论，设指数为 n，

  • 当 n 为偶数时，$x^n = (x^2)^{n/2}$;
  • 当 n 为奇数时，$x^n = (x^2)^{n//2}*x$ ($n//2$ 表示向下取整)。

可以看到，最终的答案分为两部分，一个是 x 的乘方部分，一个是额外的 乘子 - 当奇数时会产生。

根据上述分析，得到如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1.0;
        long a = n;     // Notice!!!
        if(a < 0){
            x = 1/x;
            a = -a;
        }
        double res = x, ext = 1.0;
        while(a > 1){
            if((a & 1) == 1){
                ext = ext * res;
                res = res * res;  
            }else{
                res = res * res;
            }
            a = a >> 1;
        }
        return res*ext;
    }
}

需要注意的是，这里将指数先放置到了 long 型的变量当中，主要是因为 int 的范围为 $2^{-31} 到 2^{31}-1$，所以，当 n 为 $2^{-31}$ (-2147483648) 的时候，n = -n; 会出现溢出问题。所以这里先将 n 放置到了一个 long 型的整数中，从而避免了该问题。

根据题解，上述的代码可以进一步精简，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        // 直接使用 res 存放奇数时产生的额外乘子
        // 乘方部分存储在 x 中，并在最后指数等于 1 的时候，将 x 乘到 res 中
        // 这么做还有个好处，统一了 n 等于 0 的情况
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}