面试官揪心一问:不使用算术运算符如何实现加减乘除

电玩女神 2021-09-07 19:34 311阅读 0赞

### 记得有次面试，面试官问了我这样一个问题：不使用加法运算符，如何实现加法运算？ ###

#### 当时看到这个问题直接把我愣住了，因为工作多年确实没想过这个问题，当时的感觉就好像我一个多年驾龄的老司机突然被交警逮到考我这台车的发动机原理是什么。你说动不动发动机原理跟我开车有关系吗？好像也有关系，但是影响我开车吗？好像也没什么影响，除非那天汽车半路抛锚了估计还是能抢救一下吧。 ####

#### 既然问到了这个问题，自然还是要回答一下的，我当时能想到答案就是通过位运算符去对两个数的二进制从低到高进行比较。 ####

#### 主要分为以下几种情况： ####

1.  同位异号：存在进1的情况下，结果位置为0，且向高位进1，否则置为1；
2.  同位都是1：存在进1的情况下，结果位置为1，且向高位进1，否则置为0；
3.  同位都是0：存在进1的情况下，结果位置为1，否则置为0；

首先有个标志位flag表示是否存在进1的情况；然后通过对1的移位操作，逐个从低位到高位对两个操作数的比特位进行&运算，判断其对应位置的数是否为1：

具体代码如下：

public static int add(Integer a, Integer b) {
            int i = 1;
            int result = 0;
            boolean flag = false;  //进位的标记
            do {//第几次循环就对应第几个bit位
                int ai = a & i;
                int bi = b & i;
                if(ai > 0 && bi > 0){ //a和b在同一bit位都是1
                    if(flag){
                        result ^= i;
                    }
                    flag = true; // true代表了2进1
                }else if((ai ^ bi) != 0){  //a和b在同一bit位有1个1和1个0的情况
                   if(flag){
                       flag = true;
                   }else{
                       //低一位没有进1的情况下,result在该bit位置为1
                       //0 ^ 1 = 1
                       result ^= i;
                   }
                }else if(flag){//a和b在同一bit位都是0的情况,有进位则该bit位置为1
                   result ^= i;
                   flag = false;
                }
                i <<= 1;  // i左移一位
            }while (i != 0);
            return result;
        }

#### 记得当时思考良久才讲出一点思路来，没想到后来面试官又是揪心一问，那么如何实现减法呢？ ####

##### 说实话当时脑袋有点蒙，我当时想到的就是通过递归、逆排序比较什么的，现在想想扯的有点远，实现加法运算还算比较简单，但其实实现减法运算也不难，只不过在此之前你需要理解计算机的原码和补码的相关概念，请参考[原码、反码、补码详解][Link 1]这篇文章。 #####

##### 其实说白了，原本计算机就只有一个加法运算器而已，加减乘除都可以考它来实现，不信你看： #####

**不使用算术运算符实现减法：**

public static int minus(Integer a,Integer b){
            if(b == 0){
                return a;
            }else{
                // b为负数情况下：(b ^ 0x7FFFFFFF) + 1 ^ 0x80000000 等于 b的绝对值
                // 即 a - b = a + |b|
                // b为正数情况下我们需要把b转为负数
                // b mod (0x1 0000 0000) = (b ^ 0xFFFF FFFF)
                // a - b 相当于 a + (-b)
                // (b ^ 0xFFFFFFFF) + 1 = (b ^ 0x80000000 ^ 0x7FFFFFFF) + 1 等于把b置为负数求其反码，最后加一就是补码
                return add(a, add(b ^ 0xFFFFFFFF, 1) );
            }
        }

**那么不使用算术运算符如何实现乘法运算呢？**

版本1：通过穷举的实现，通过累加求和，比如a\*b其实就是b个a相加求和嘛。

public static int multiply(Integer a , Integer b){
            return multiplyV1(a,b);
        }
    
        //乘法v1 类似穷举法的思想进行累加
        public static int multiplyV1(Integer a,Integer b){
            int result = 0;
            boolean flag = false;
            if(b < 0){
                b = abs(b);   //取b的绝对值
                if(a > 0){  // ab异号情况下
                    flag = true;
                }else{
                    a = abs(a);   //取a的绝对值
                }
            }
            while( b > 0){
                result = add(result,a);; // b个a相加
                b = minus(b,1);
            }
            if(flag){ //ab异号则result必为负数
                result = add((result ^  0xFFFFFFFF) , 1);      //对a的符号位取反求再其补码
            }
            return result;
        }

但是上面的算法效率实在是太低，如果b有几百万上千万，那你这性能都慢到什么程度?

后来我又琢磨出了一套优化的算法,版本二：

//乘法v2  优化版
        public static int multiplyV2(Integer a,Integer b){
            int result = 0;
            boolean flag = false;
            if(b < 0){
                b = abs(b);   //取b的绝对值
                if(a > 0){  // ab异号情况下
                    flag = true;
                }else{
                    a = abs(a);   //取a的绝对值
                }
            }
            //最多循环七次
            while (b > 0){
                if((b & 1) == 0){
                    a <<= 1;
                    b >>= 1;
                }else{
                    result = add(result,a);
                    b ^= 0x00000001;
                }
            }
            if(flag){ //ab异号则result必为负数
                result = add((result ^  0xFFFFFFFF) , 1);      //对a的符号位取反求再其补码
            }
            return result;
        }

**最后一个问题，也是最难的，不使用算术运算符实现除法运算**

我当时也是想了许久，然后我就想乘法既然可以累加，为什么除法就不能累减呢？思路一转，解法就来了，a/b无非就是找出a里面有几个b吗，这还不好办：

public static int divide(Integer a,Integer b){
            if(b == 0){
                throw new IllegalArgumentException("除数不能为0");
            }
            int result = 0;
            boolean flag = false;
            if((a ^ b) < 0){
                flag = true;
            }
            a = abs(a);
            b = abs(b);
            if(a < b){
                return 0;
            }
            a = minus(a,b);
            while(a >= 0){
                a = minus(a,b);
                result = add(result,1);
            }
            if(flag){ //ab异号则result必为负数
                result = add((result ^  0xFFFFFFFF) , 1);      //对a的符号位取反求再其补码
            }
            return result;
        }

##### 最后附上我的测试用例以及取绝对值的方法 #####

//求a的绝对值
        public static int abs(Integer a){
            if(a >= 0){
                return a;
            }
            //a为负值情况下取a的补码再对其符号位取反就是其绝对值
            //等价于 add(b ^ 0xFFFFFFFF, 1)
            return add((a ^ 0x7FFFFFFF) , 1) ^ 0x80000000;
        }
    
        public static void check(String methodName) throws Exception {
            Class aclass = Arithmetic.class;
            Method method = aclass.getMethod(methodName, Integer.class, Integer.class);
            Random random = new Random();
            for(int i = 0;i < 1000;i++) {
                //生成[-1000,1000]的随机数
                Integer a = random.nextInt(2000) - 1000;
                Integer b = random.nextInt(2000) - 1000;
                int result = (int) method.invoke(aclass, a, b);
                switch (methodName){
                    case "add" : if (result != (a + b)) {
                        //若是实现的算法计算结果不对，直接抛出错误
                        throw new Exception(methodName+"方法计算错误！！！参与计算的值：a=" + a + ",b=" + b +
                                ";计算结果为："+result+",正确结果为："+(a+b));
                    };break;
                    case "minus" : if (result != (a - b)) {
                        //若是实现的算法计算结果不对，直接抛出错误
                        throw new Exception(methodName+"方法计算错误！！！参与计算的值：a=" + a + ",b=" + b +
                                ";计算结果为："+result+",正确结果为："+(a-b));
                    };break;
                    case "multiply" : if (result != (a * b)) {
                        //若是实现的算法计算结果不对，直接抛出错误
                        throw new Exception(methodName+"方法计算错误！！！参与计算的值：a=" + a + ",b=" + b +
                                ";计算结果为："+result+",正确结果为："+(a*b));
                    };break;
                    case "divide" : if (result != (a / b)) {
                        //若是实现的算法计算结果不对，直接抛出错误
                        throw new Exception(methodName+"方法计算错误！！！参与计算的值：a=" + a + ",b=" + b +
                                ";计算结果为："+result+",正确结果为："+(a/b));
                    };break;
                }
    
                System.out.println("a="+a+",b="+b+",result="+result);
            }
        }
    
        @Test
        public void test1() throws Exception {
            check("add");
        }
    
        @Test
        public void test2() throws Exception {
            check("minus");
        }
    
        @Test
        public void test3() throws Exception {
            check("multiply");
        }
    
        @Test
        public void test4() throws Exception {
            check("divide");
        }
    
        public static void main(String[] args) throws Exception {
            check("add");
            check("minus");
            check("multiply");
            check("divide");
    
        }

GitHub源码地址：[git@github.com:HelloWorld19930603/alien\_cat.git][git_github.com_HelloWorld19930603_alien_cat.git]  
本文章源码对应目录：alien\_cat/algorithm/src/main/java/com/aliencat/javabase/bit

[Link 1]: https://blog.csdn.net/c15158032319/article/details/116801548
[git_github.com_HelloWorld19930603_alien_cat.git]: https://github.com/HelloWorld19930603/alien_cat