算法通关村十一关 | 位运算实现加法和乘法-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村十一关 | 位运算实现加法和乘法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.位实现加法和乘法

在计算机中，位运算的效率要比加减乘除的效率更高，因此在高性能软件中源码中大量使用，计算机里各种运算基本上都是位运算。

学习下面内容之前建议先学习位运算规则：算法通关村十一关 | 位运算的规则_我爱学算法的博客-CSDN博客

1.1 位运算实现加法

题目：LeetCode371

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

示例1：

输入： a =1，b = 2

输出：3

我们先看两个二进制位相加的情况：

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0（发生进位，应该是10）

相加的时候我们需要考虑两个问题：进位部分是什么，不进位部分是什么，从上面的情况可以看到，对于a和b两个数不进位部分的情况是：相同为0，不同为1，就是a⊕b。

对于进位部分，只有a和b都是1的时候才会进位，而且进位只能是1，这不就是a&b=1吗？然后位数由一位变成两位，只需将1手动移位一下就好，也就是（a & b）<< 1。

结论：

不进位部分：用a⊕b计算

是否进位，以及进位的值使用（a & b）<< 1计算，只有结果为1的时候才会出现进位

异或不用考虑是否进位

我们可以将整数a和b的和，拆分成a和b的无进位加法结果与进位结果的和，

    //位运算加法
    public int getNum(int a, int b){
        while (b != 0){
            int sign = (a & b) << 1;
            a = a ^ b;
            b = sign;
        }
        return a;
    }

注意：需要思考的是，a异或于移位之后的（a & b）的情况，第一次并没有考虑进位，第二次才进行进位，

2.2 递归乘法

题目：LeetCode里面面试08.05

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

示例1：

输入：A = 1，B = 10

输出：10

如果使用累加来计算，效率太低，还是要用移位运算。

首先，求得A和B的最大值和最小值，对其中的最小值当作乘数（为什么选最小值当乘数，因为可以计算的更少），将其拆分成2的幂的和，比如12用二进制表示：1100，即1000 + 0100。0 * 2^0 + 0 * 2^1 + 0 * 2^2 + 1 * 2^3,和0 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3的和。

13 * 12 = 13 * ( 8 + 4) = 13 * 8 + 13 * 4 = (13 << 3) + (13 << 2);

代码实现：文章来源地址https://www.toymoban.com/news/detail-665166.html

    //位运算乘法
    public int multiply2(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的时候累加
            if ((min & 1) == 1){
                ans += max << i;
            }
            min >>= 1;
        }
        return ans;
    }

到了这里，关于算法通关村十一关 | 位运算实现加法和乘法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！