Java进阶篇：用位运算实现加、减、乘、除

╰+哭是因爲堅強的太久メ 2024-04-18 13:11 19阅读 0赞

首先明确原码、反码、补码的概念

计算机系统中，数值一律用**补码**来表示：因为补码可以使符号位和数值位统一处理，同时可以使减法按照加法来处理。

对补码做简单介绍：数值编码分为原码，反码，补码，符号位均为0正1负。

原码 -> 补码： 数值位取反加1

补码 -> 原码： 对该补码的数值位继续 取反加1

补码 的绝对值（称为真值）：正数的真值就是本身，负数的真值是各位（包括符号位）取反加1（即变成原码并把符号位取反）.

### 加法： ###

将一个整数用二进制表示，其加法运算就是：相异或（^）时，本位为1，进位为0；同为1时本位为0，进位为1；同为0时，本位进位均为0.

所以，不计进位的和为sum = a^b，进位就是c = a&b,(与sum相加时先左移一位，因为这是进位）。完成加法直到进位为0.

public static void main(String[] args) {
            add(11, 12);
        }
    
        private static int add(Integer a, Integer b) {
    
            Integer sum = a;
            while (b != 0) {
                //a与b无进位相加
                sum = a ^ b;
                b = (a & b) << 1;
                a = sum;
            }
            return sum;
        }
    
    运算过程
        a = 11 = 1011
        b = 12 = 1100
    
        1. sum = a ^ b = 1011 ^ 1100 =  00111
        2. b = (a & b) << 1 = ( 1011 & 1100 ) << 1 =  10000
        3. a = sum = 00111
        4. b != 0
        5. sum = a ^ b = 00111 ^ 10000 = 10111
        6. b = (a & b) << 1 = ( 00111 & 10000 ) << 1 =  000000
        7. a = sum = 10111
        8. b == 0 break;
        9. sum = 10111 = 23

sum = a ^ b 应该很好理解，1 + 1 =0 ； 1 + 0 = 1 ； 0 + 0 = 0;

比较难理解的是 b = (a & b) << 1 ； a&b之后得到的就是进位情况，1011 & 1100 =》 1000 即 a+b 在最高为产生了进位，由于是进位给前一位，所以还需要左移一位。（看不懂就自己写两道题）

### 减法： ###

a-b  = a+(-b) ，所以我们要先对b取相反数，再相加。求相反数就需要先将各位取反后+1；

5 **->** 0....0101  **-取反->** 1.....1010 **-+1->** 1....1011 **->**\-5

取反后再用加法加起来即可。

/**
         *     求相反数：将各位取反加一
         */
        private static int negative(int num)     
        {
            return add(~num, 1);
        }
        /**
         *    减法
          */
        private static int Minus(int a, int b) {
            return add(a, negative(b));
        }

### 乘法： ###

**乘法**：原理上还是通过加法计算。将b个a相加，注意下面实际的代码。

//乘法
        private static int multi(int a, int b) {
            //将乘数和被乘数都取绝对值　
            int multiplicand = a < 0 ? add(~a, 1) : a;
            int multiplier = b < 0 ? add(~b, 1) : b;
    
            int res = 0;
            // 判断multiplier 任何数*0=0
            while (multiplier != 0) {
                //判断 multiplier 是不是 奇数
                if ((multiplier & 1) != 0) {
                    // 如果是奇数 则加上一次multiplicand本身
                    res = add(res, multiplicand);
                }
                // multiplicand * 2
                multiplicand <<= 1;
                // multiplier  / 2
                multiplier >>>= 1;
            }
            //计算乘积的符号　　
            if ((a ^ b) < 0) {
                res = add(~res, 1);
            }
            return res;
        }

debug跑两遍就能理解精髓，就是当 multiplier 是偶数时，则每次让 multiplicand \* 2 直到 multiplier / 2 = 0时。当b时奇数是，先加上单独的那个 multiplicand，再重复 multiplier 为偶数的步骤。

我们举个例子

multiplicand=10， multiplier = 5 答案自然是50 。

我们来看看核心步骤

1.   multiplier 是奇数 则先加上当前的 multiplicand，res = 10；
2.   multiplicand << 1 = 20; multiplier >>> 1 = 2; (这里应该看出了一些感觉了)
3.   multiplier 是偶数 if为false，则 multiplicand << 1 = 40;  multiplier>>>1 = 1; 
4.   multiplier 是奇数 res + multiplicand  = 50; multiplicand << 1 = 80 ; multiplier>>>1 = 0;
5.   循环结束 res = 50；

### 正数除法： ###

计算机是一个二元的世界，所有的int型数据都可以用\[2^0, 2^1,...,2^31\]这样一组基来表示（int型最高31位）。

不难想到用除数的2^31,2^30,...,2^2,2^1,2^0倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。

private static int divide(int a,int b) {
            // 先取被除数和除数的绝对值
            int dividend = a > 0 ? a : add(~a, 1);
            int divisor = b > 0 ? a : add(~b, 1);
            int quotient = 0;// 商
            int remainder = 0;// 余数
            for(int i = 31; i >= 0; i--) {
                // 比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，
                // 而是用(dividend>>i)与divisor比较，
                // 效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，
                // 如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor
                if((dividend >> i) >= divisor) {
                    quotient = add(quotient, 1 << i);
                    dividend = minus(dividend, divisor << i);
                }
            }
            // 确定商的符号
            if((a ^ b) < 0){
                // 如果除数和被除数异号，则商为负数
                quotient = add(~quotient, 1);
            }
            // 确定余数符号
            remainder = b > 0 ? dividend : add(~dividend, 1);
            System.out.println("余数："+ remainder);
            // 返回商
            return quotient;
        }

这个应该很好理解。