本文的网课内容学习自B站左程云老师的算法详解课程，旨在对其中的知识进行整理和分享~

网课链接：算法讲解033【必备】位运算实现加减乘除_哔哩哔哩_bilibili

一.两数相除

题目：两数相除

算法原理

• 整体思路

  • 这个算法旨在仅使用位运算来实现整数的加、减、乘、除操作。通过巧妙地利用位运算的特性，如异或（无进位相加）、与（获取进位）、移位（乘以或除以2的幂次方）等操作来模拟算术运算。

• 具体原理

  • 加法（add方法）
    • 利用异或操作实现无进位相加：ans = a ^ b。异或操作在两个对应位不同时结果为1，相同为0，这类似于不考虑进位的加法。
    • 利用与操作获取进位并左移1位：b = (a & b) << 1。与操作得到的是两个数相加时产生进位的位置，左移1位就是将进位加到下一位。
    • 重复上述步骤直到进位b为0，此时ans就是a和b相加的结果。
  • 减法（minus方法）
    • 基于加法和取反操作实现减法，根据数学原理a - b=a+( - b)，所以调用add方法并传入a和neg(b)来实现减法操作。
  • 取反（neg方法）
    • 先对整数n按位取反~n，然后再加上1就实现了取反操作。这是基于计算机中负数的表示方法（补码表示），补码就是原码按位取反再加1。
  • 乘法（multiply方法）
    • 采用类似于手动计算乘法的方法，从最低位开始逐位处理。
    • 如果b的最低位为1（(b & 1)!= 0），就将a加到结果ans中，这相当于在做乘法时，如果乘数的某一位是1，就加上被乘数乘以对应的权值（2的幂次方）。
    • 然后a左移1位（a <<= 1），相当于被乘数乘以2；b右移1位（b >>>= 1），相当于乘数除以2。
    • 重复上述步骤直到b为0，此时ans就是a和b相乘的结果。
  • 除法（divide方法）
    • 特殊情况处理：
      • 如果a和b都是整数最小值，根据题目要求返回1。
      • 如果b是整数最小值，而a不是，结果为0。
      • 如果a是整数最小值，b是 - 1，按照要求返回整数最大值。
    • 对于a和b都不是整数最小值的情况（调用div方法）：
      • 首先将a和b转换为正数（如果是负数就调用neg方法取反）。
      • 从最高位（30位，对于32位整数）开始，逐位判断。如果x（a转换后的正数）右移i位后的值大于等于y（b转换后的正数），则商的第i位为1，并更新x的值（减去已经计算的部分，即y乘以2的i次方）。
      • 根据a和b的正负情况，对结果进行调整（如果一正一负则取反）。
      • 如果a是整数最小值，b不是整数最小值且不是 - 1，先将a调整为可以正常进行div函数计算的数，然后计算div，最后对结果进行调整并返回。

代码实现

// 不用任何算术运算，只用位运算实现加减乘除
// 代码实现中你找不到任何一个算术运算符
// 测试链接 : https://leetcode.cn/problems/divide-two-integers/
// 定义一个类，类名为BitOperationAddMinusMultiplyDivide
public class BitOperationAddMinusMultiplyDivide {
    // 定义一个常量MIN，表示整数的最小值
    public static int MIN = Integer.MIN_VALUE;

    // 除法函数，用于计算a除以b的结果
    public static int divide(int a, int b) {
        // 如果a和b都是整数最小值，根据题目要求返回1
        if (a == MIN && b == MIN) {
            return 1;
        }
        // 如果a和b都不是整数最小值，调用div函数进行正常的除法计算
        if (a!= MIN && b!= MIN) {
            return div(a, b);
        }
        // 如果b是整数最小值，而a不是，根据除法规则，结果为0
        if (b == MIN) {
            return 0;
        }
        // 如果a是整数最小值，b是 - 1，按照题目要求返回整数最大值
        if (b == neg(1)) {
            return Integer.MAX_VALUE;
        }
        // 如果a是整数最小值，b不是整数最小值且不是 - 1
        // 先将a调整为可以正常进行div函数计算的数
        a = add(a, b > 0? b : neg(b));
        int ans = div(a, b);
        int offset = b > 0? neg(1) : 1;
        // 最后对结果进行调整并返回
        return add(ans, offset);
    }

    // 这个函数用于在a和b都不是整数最小值的情况下进行除法计算
    public static int div(int a, int b) {
        // 如果a是负数，将其转换为正数（通过neg函数取反）
        int x = a < 0? neg(a) : a;
        // 如果b是负数，将其转换为正数（通过neg函数取反）
        int y = b < 0? neg(b) : b;
        int ans = 0;
        // 从最高位（30位，对于32位整数来说）开始，逐位判断并计算商
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            // 如果x右移i位后的值大于等于y
            if ((x >> i) >= y) {
                // 则商的第i位为1
                ans |= (1 << i);
                // 更新x的值，减去已经计算的部分（y乘以2的i次方）
                x = minus(x, y << i);
            }
        }
        // 根据a和b的正负情况，对结果进行调整（如果一正一负则取反）
        return a < 0 ^ b < 0? neg(ans) : ans;
    }

    // 加法函数，通过位运算实现加法
    public static int add(int a, int b) {
        int ans = a;
        // 当b不为0时，表示还有进位需要处理
        while (b!= 0) {
            // ans为a和b无进位相加的结果（异或操作实现无进位相加）
            ans = a ^ b;
            // b为a和b相加时的进位信息（与操作得到进位，再左移1位）
            b = (a & b) << 1;
            a = ans;
        }
        return ans;
    }

    // 减法函数，通过加法和取反操作实现减法（a - b=a+( - b))
    public static int minus(int a, int b) {
        return add(a, neg(b));
    }

    // 取反函数，通过先按位取反再加1的方式实现取反
    public static int neg(int n) {
        return add(~n, 1);
    }

    // 乘法函数，通过位运算实现乘法，也称为龟速乘
    public static int multiply(int a, int b) {
        int ans = 0;
        // 当b不为0时，继续计算乘法
        while (b!= 0) {
            // 如果b的最低位为1（即b为奇数）
            if ((b & 1)!= 0) {
                // 将a加到结果ans中
                ans = add(ans, a);
            }
            // a左移1位，相当于a乘以2
            a <<= 1;
            // b右移1位，相当于b除以2
            b >>>= 1;
        }
        return ans;
    }
}