算法通关村第十一关—位运算的高频算法题(白银)

发布时间:2024年01月13日

?????位运算的高频算法题

一、位移的妙用

1.1 位1的个数

?LeetCode191 编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为1’的个数。题目给定的n是32位二进制表示下的一个整数。

示例1:
输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串00000000000000000000000000001011中,共有三位为'1'。
示例2:
输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串00000000000000000000000010000000中,共有一位为'1'

解法一:遍历的二进制表示的每一位,判断每一位是否为1,同时进行计数。
那问题就是如何通过位运算来识别到1,例如:00001001001000100001100010001001,首先我们注意到要识别到最低位的1,可以这么做:

00001001001000100001100010001001
&00000000000000000000000000000001
=00000000000000000000000000000001

?也就说将原始数字和1进行&运算就能知道最低位是不是1了,那其他位置怎么算呢?我们可以有两种思路,让1不断左移或者将原始数据不断右移。
?例如将原始数据右移就是:

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

?让1不断左移:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        for(int i = 0; i < 32; i++){
            if((n & (1 << i)) != 0) //注意不能直接sum+=(n & (1 << i))
            sum++;
        }
        return sum;
    }
}

解法二:
?上面的代码写出来,这个题基本就达标了,但这还不是最经典的解法,我们继续分析:按位与运算有一个性质:对于整数n,计算n&(n一1)的结果为将n的二进制表示的最后一个1变成0。利用这条性质,令n=n&(n一1),则n的二进制表示中的1的数量减少一个。重复该操作,直到n的二进制表示中的全部数位都变成0,则操作次数即为的位1的个数。

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

1.2 比特位计数

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

示例1:
输入:n=2
输出:[0,1,1]
解释:0到n有012三个数字,每个数字含有1的个数分别为0 1 1个,如下:
0-->0
1-->1
2-->10
示例2:
输入:n=5
输出:[0,1,1,2,1,2]
解释:0到有012345六个数字,每个数字含有1的个数分别为0,1,1,2,1,2个,如下:
0-->0
1-->1
2-->10
3-->11
4-->100
5-->101

?利用上一道题计算中提到的性质:n&(n一1)的结果为将n的二进制表示的最后一个1变成0,可以很好地解决这道题

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

1.3 颠倒无符号整数

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

示例1:
输入:n=00000010100101000001111010011100
输出:964176192(00111001011110000010100101000000)
解释:输入的二进制串00000010100101000001111010011100
表示无符号整数43261596,
因此返回964176192,其二进制表示形式为00111001011110000010100101000000.
示例2:
输入:n=11111111111111111111111111111101
输出:3221225471(10111111111111111111111111111111)
解释:输入的二进制串11111111111111111111111111111101表示无符号整数4294967293,
因此返回3221225471其二进制表示形式为10111111111111111111111111111111

?首先这里说是无符号位,那不必考虑正负的问题,最高位的1也不表示符号位,这就省掉很多麻烦。
?可以注意到对于n的二进制表示的从低到高第ⅰ位,在颠倒之后变成第31-ⅰ位(0≤i<32),所以可以从低到高遍历的二进制表示的每一位,将其放到其在颠倒之后的位置,最后相加即可。
看个例子,为了方便我们使用比较短的16位演示:

原始数据:1001 1111 0000 0110(低位)
第一步:获得n的最低位0,然后将其右移16-1=15位,得到:
reversed:0*** **** **** ****
n右移一位:0100 1111 1000 0011
第二步:继续获得上面n的最低位1,然后将其右移15-1=14位,并与reversed相加得到:
reversed:01** **** **** ****
n右移一位:0010 0111 1100 0001
继续,一直到n全部变成0

代码如下

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

二、位实现加减乘除专题

2.1 位运算实现加法

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

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

既然不能使用+和-,那只能使用位运算了。我们看一下两个二进制位相加的情况:

[1]0+0=0
[2]0+1=1
[3]1+0=1
[4]1+1=0
(发生了进位,应该是10)

?两个位加的时候,我们无非就考虑两个问题:进位部分是什么,不进位部分是什么。从上面的结果可以看到,对于a和b两个数不进位部分的情况是:相同为0,不同为1,这不就是a⊕b吗?
而对于进位,我们发现只有a和b都是1的时候才会进位,而且进位只能是1,这不就是a&b=1吗?然后位数由1位变成了两位,也就是上面的[4]的样子,那怎么将1向前挪一下呢?手动移位一下就好了,也就是(a&b)<<1。所以我们得到两条结论:
1.不进位部分:用a⊕b计算就可以了。
2.是否进位,以及进位值使用(a&b)<<1计算就可以了。
于是,我们可以将整数a和b的和,拆分为a和b的无进位加法结果与进位结果的和,代码就是:

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

2.2 递归乘法

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

示例1:
输入:A=1,B=10
输出:10

示例2:
输入:A=3,B=4
输出:12

?如果不让用 * 来计算,一种是将一个作为循环的参数,对另一个进行累加,但是这样效率太低,所以我们还是要考虑位运算。
?首先,求得A和B的最小值和最大值,对其中的最小值当做乘数(为什么选最小值,因为选最小值当乘数,可以算的少),将其拆分成2的幂的和,即min=a020+a1*21+.+ai2i+…其中ai取0或者1。其实就是用二进制的视角去看待min,比如12用二进制表示就是1100,即1000+0100。例如:
1312=13(8+4)=138+134=(13<<3)+(13<<2);
?上面仍然需要左移5次,存在重复计算,可以进一步简化:
?假设我们需要的结果是ans,定义临时变量:tmp=13<<2=52计算之后,可以先让ans=52,然后tmp继续左移一次tmp=52<1=104,此时再让ans=ans+tmp这样只要执行三次移位和一次加法,实现代码:

class Solution {
    public int multiply(int A, int B) {
        int max = Math.max(A,B);
        int min = Math.min(A,B);
        int sum = 0;
        while(min != 0){
            if((min & 1) == 1){ //判断第一位
                sum += max;
            }
            min = min >> 1;//右移一位,相当于除以2
            max *= 2; //max乘2,用来弥补min右移
        }
        return sum;
    }
}
文章来源:https://blog.csdn.net/m0_73709096/article/details/135574697
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。