当前位置:   article > 正文

位运算之实现加减乘除_按位运算和乘法运算组合

按位运算和乘法运算组合

由于不是科班出生,对位运算一直产生抗拒心理,今天接触到相关算法题:用位运算实现加减乘除,在此记录下来。

位运算实现加法

大致分三步:

  1. 先求两数不带进位的加法:a和b异或的值
  2. 再求两数进位的值:a和b与的结果左移一位
  3. 将1,2相加(这里的加法又是以上的2步完成,直到没有进位)

贴代码:

	public static int add(int a,int b){
        int sum = a;
        while (b != 0){
            sum = a ^ b;    //将a,b两值不带进位相加
            b = (a & b) << 1; //b更新为进位的值
            a = sum;   //a更新为不带进位的相加值
        }
        return sum;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

位运算实现减法

减法就是:a - b = a + (- b)。说一下-b的实现(发现自己之前都理解错了 )。
在计算机内存中存放的都是数值的补码(正数的补码为原码本身,负数的补码为原码符号位不变其余位取反然后结果加1;正数的反码为源码本身,负数的反码为原码符号位不变其余位取反)。

下面讲一下~9这个操作在计算机中实现的步骤:(假设是8位的)
+9 原码:0000 1001
+9 补码:0000 1001 (实际存放的值)
~按位取反后原码:1111 0110
补码:1000 1010 (实际存放值)
也就是~9的输出会是-10。

那么再看一下~(-9)这个操作:
-9 原码:1000 1001
-9 补码:1111 0111
~按位取反后原码:0000 1000
补码:0000 1000
~(-9)的输出是8。

找到规律了,要求a的相反数,就是 (~a) + 1

贴代码:

	public static int minus(int a,int b){
        return add(a,neg(b));
    }

    public static int neg(int b){ //求相反数
        return add(~b,1);
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

位运算实现乘法

这个要结合平时做乘法的逻辑,聪慧的你一定知道怎么做,(本人比较懒)这里就不画图了。
若要计算a*b,分以下几步:(先定义一个res变量表示结果)

  1. b的最后一位如果为1,res加上a,b的最后一位如果为0,当然就不加啦;(这里加法仍然要用位运算)
  2. 将b右移1位,a左移一位,为下次运算做准备;
  3. 重复1,2步直到b为0。

贴代码:

	public static int multiply(int a,int b){
        int res = 0;
        while (b != 0){
            if ((b & 1) != 0){
                res = add(res,a);
            }
            a <<= 1;
            b >>>= 1;//无符号右移
        }
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

位运算实现除法

思路是:为了求 res = a / b,则 a = res * b,为了演说方便,假如 res = 9,其二进制为1001,则
a = (1 * 23 + 0 * 22 + 0 * 21 +1 * 20 ) * b = b * 23 + b * 20
问题就转化为如何求2的指数了。
要注意的是:负数全部先转化为正数来做,最后再根据符号转成相应的结果,但是由于Integer的负数最小转化为正数会溢出,所以要特殊处理。
贴代码:

	public static int divide(int a ,int b){
        if (b == 0){
            throw new RuntimeException("num/0");
        }else if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE){
            return 1;
        }else if (b == Integer.MIN_VALUE) {
            return 0;
        }else if (a == Integer.MIN_VALUE){ //最小值求相反数会溢出
            int res = div(add(a,1),b); //先把最小值+1,再转换成正数做除法
            res = add(res,div(minus(a,multiply(res,b)),b)); //  res + (a - res * b) / b
            return res;
        }else {
            return div(a,b);
        }
    }

    public static int div(int a,int b){ //核心代码
        int x = a < 0 ? neg(a) : a; // 如果为负数,求相反数
        int y = b < 0 ? neg(b) : b;
        int res = 0;
        for(int i = 31;i > -1;i = minus(i,1)){
            if ((x >> i) >= y){ //将res的最高位记录下来,从高位开始记录
                res |= 1 << i;
                x = minus(x,y << i);
            }
        }
        res = ((a < 0 && b <0) || (a > 0 && b < 0)) ? neg(res) : res;
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/830099
推荐阅读
相关标签
  

闽ICP备14008679号