位运算的高频算法题

这里看之前,先来想一想&^符号有哪些特点?

  • 任何二进制码a 对于: a&1 = a
  • 二进制数a^b 等价于: 无进位的相加
  • 2的二进制为 010, 4的二进制为100 ,进行或运算,其结果为 110 .其值为6;也就说|=运算可以进行加法操作。

即:

int res = 2;
res |= 4; 
print(res); // 6

1.位移的妙用

1.1 L191 位1的个数

LeetCode191 编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数。

题目给定的 n 是 32 位二进制表示下的一个整数,计算位 1 的个数的最简单的方法是遍历 n 的二进制表示的每一位,判断每一位是否为 1,同时进行计数。

问题便是如何确定最低位是否为1,可以:

00001001001000100001100010001001
 & 00000000000000000000000000000001
 = 00000000000000000000000000000001

得到代码

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i =0;i<32;i++){
            count+= (n>>i)&1;
        }
        return count;
    }
}

拓展问题:16进制时怎么统计0000 00de

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i =0;i<32;i++){
            count+= (n>>i)&1;
        }
        return count;
    }
}

另一种经典的解法

我们知道公式: n&(n-1)

意味着: 对于整数 n,计算n & (n−1) 的结果为将 n 的二进制表示的最后一个 1 变成 0。

也就是说执行了m次当n变为0,m就是1的次数,代码如下:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0){
            n = n&(n-1);
            count++;
        }
        return count;
    }
}

上面两种解法,第一种的循环次数取决于原始数字的位数,而第二种的取决于1的个数,效率自然要高出不少,使用n = n & (n - 1)计算是位运算的一个经典技巧,该结论可以完美用到下面的338题目中:

源码教你做人

首先大家对Java的bitCount应该不陌生,该方法可以直接统计某个数中二进制数1的格式

public class Solution {
    private static final int M1 = 0x55555555; // 01010101010101010101010101010101
    private static final int M2 = 0x33333333; // 00110011001100110011001100110011
    private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111
     public int hammingWeight(int n) {
        n = n - ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        n = (n + (n >>> 4)) & 0x0f0f0f0f;
        n = n + (n >>> 8);
        n = n + (n >>> 16);
        return n & 0x3f;
    }
}

1.2 L338比特位计数

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

利用上道题的方法,但是这里需要重新定义一个变量j

class Solution {
    public int[] countBits(int n) {
        int[] arr = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int j = i;
            while (j != 0) {
                j = j & (j - 1);
                count++;
            }
            arr[i] = count;
        }
        return arr;
    }
}

另一种写法:

class Solution {
    public int[] countBits(int n) {
        int[] arr = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            arr[i] = countOnes(i);
        }
        return arr;
    }

    public static int countOnes(int x) {
        int count = 0;
        while (x != 0) {
            x &= (x - 1);
            count++;
        }
        return count;
    }
}

综合来说,时间复杂度为 n * logn

或是使用n不断右移

    public int[] countBits(int num) {
            int[] bits = new int[num + 1];
            for (int i = 0; i <= num; i++) {
                for (int j = 0; j < 32; j++) {
                    bits[i] += (i >> j) & 1;
                }
            }
            return bits;
        }

时间复杂度为: n = num + 1 => o(32n)

1.3 L190颠倒二进制位

LeetCode190 .颠倒给定的 32 位无符号整数的二进制位。 提示:输入是一个长度为32的二进制字符串。

这道题做法为:先得到最低位的数字,然后将最低位的数字左移32-i 个地方得到反转后的位置

但是记得这里提前使用的res为0 ,因此可以使用|=来进行结果的构建,

例如:101 左移后得到 100 之后|= 001 得到结果101

这里还需要记得每一次移动,需要将n>>1

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for(int i =1;i<=32;i++){
            res |= (n&1)<<(32-i);
           n>>>=1;
        }
        return res;
    }
}

分治的解法

这种方法在JDK、Dubbo等源码中都能见到,特别是涉及协议解析的场景几乎都少不了位操作。积累相关的技巧,可以方便面试,也有利于阅读源码。

public class Solution {
    private static final int M1 = 0x55555555; // 01010101010101010101010101010101
    private static final int M2 = 0x33333333; // 00110011001100110011001100110011
    private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111

    public int reverseBits(int n) {
        n = n >>> 1 & M1 | (n & M1) << 1;
        n = n >>> 2 & M2 | (n & M2) << 2;
        n = n >>> 4 & M4 | (n & M4) << 4;
        n = n >>> 8 & M8 | (n & M8) << 8;
        return n >>> 16 | n << 16;
    }
}

2.位实现加减乘除专题

L371 两个整数之和

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

示例 1:

输入:a = 1, b = 2
输出:3
示例 2:

输入:a = 2, b = 3
输出:5

这里对情况进行分析

[1] 0 + 0 = 0
[2] 0 + 1 = 1
[3] 1 + 0 = 1
[4] 1 + 1 = 0 

这里可以发现: 相同为0,不同为1 ,符合 ^ 运算

那么进位怎么算呢?

我们可以提前把需要进位的地方进号位,进位的规律很明显可以得到: (a&b)<<1

如图:

image-20240305093113978

得知这两个特性,现在只需要解决加法了,这个时候可以看如图的规律:

异或运算与进位运算的异或运算,结果正好是结果!

可以得到初步代码

 public int getSum(int a, int b) {
      int c =  (a&b)<<1;
       int x =  a^b ;
       return x^c;
    }

但是这不完全对,因为会有多次进位的情况如: 20 和 30

当20和30 进行一轮计算后得到:

^(不进位): 0 0 0 0 1 0 1 0 (10)

&(进位): 0 0 1 0 1 0 0 0 (40)

可以发现依然在第四位上需要进位,此时我们需要重新对这两个数进行一轮运算

得到:

0 0 0 1 0 0 0 0

0 0 1 0 0 0 1 0

^运算后得到结果:50

循环有了,结束条件是什么呢?

我们可以发现当没有可以进位时,就成立了,所以我们可以取一个sign,当a&b==0结束

class Solution {
    public int getSum(int a, int b) {
        while (a != 0) {
            int sign = (a & b) << 1;
            b ^= a; //等价与 b^a = b
            a = sign;
        }
        return b; //b为最终结果
    }
}

面试题 08.05. 递归乘法

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

如果不让用*来计算,一种是将一个作为循环的参数,对另一个进行累加,但是这样效率太低,所以我们还是要考虑位运算

这道题分为两种情况:

  • A为偶数: (A/2)==(B*2)
  • A为奇数: (A/2)==(B*2)+A

过程如图,力扣用户题解:

image-20240305114603352

位运算

image-20240305114639610

可以很容易得出递归代码

class Solution {
    public int multiply(int A, int B) {
        //当不断右移减小的B为0时停止
        if (B == 0) {
            return 0;
        }
        if ((B & 1) != 0) {
            return multiply(A << 1, B >> 1) + A;
        } else {
            return multiply(A << 1, B >> 1);
        }
    }
}

在这个基础上,可以进行优化,我们发现,当右移的数越小,执行次数也会越少,因此最终代码为:

class Solution {
    public int multiply(int A, int B) {
        int min = Math.min(A, B);
        int max = Math.max(A, B);
        return chose(max, min);
    }

    public static int chose(int A, int B) {
      if (B == 0) {
            return 0;
        }
        if ((B & 1) != 0) {
            return chose(A << 1, B >> 1) + A;
        } else {
            return chose(A << 1, B >> 1);
        }
    }}

在这个基础上,我们也可以使用迭代来实现

public int multiply(int A, int B) {
        int min = Math.min(A, B);
        int max = Math.max(A, B);
        int ans = 0;
        for (int i = 0; min != 0; i++) {
        //位为1时才更新ans,否则max一直更新
            if ((min & 1) == 1) {
                ans += max;
            } 
            min >>= 1;
            max+=max; //这里没有使用位移,可以直接使用+也一样
        }
          return ans;
    }