package com.jiucaiyuan.net.question;



/**

 * 问题：给定两个有符号32位整数a和b，不能使用算数运算符，实现加、减、乘、除运算

 * 要求：如果给定a、b执行加减乘除运算结果就会导致数据的溢出，那么你实现的函数不必对此负责，

 * 除此之外，请保证计算过程不发生溢出

 * <p>

 * 直到进位d为0时，最终的a就是a和b的和

 *

 * @Author jiucaiyuan  2022/6/4 22:26

 * @mail services@jiucaiyuan.net

 */



public class Math {



    /**

     * <pre>

     * ^，异或，两个数的异或，就是无进位相加

     * &，与，两个数的与，表示两个数二进制加和时有进位，表示哪位相加后会产生进位，如果向左移动一位，就是正常的进位

     * <p>

     * 综上，对两个数a和b进行求和操作，可以转化为

     * loop (b != 0){

     * c = a^b;

     * d = (a & b) << 1;

     * a = c;

     * b = d;

     * }

     * </pre>

     *

     * @param a

     * @param b

     * @return

     */

    public static int add(int a, int b) {

        int sum = a;

        while (b != 0) {

            sum = a ^ b;  //无进位相加

            b = (a & b) << 1; //进位信息

            a = sum;

        }

        return sum;

    }



    /**

     * 返回指定数n的相反数（指定a，返回-a）

     * 一个数的取反，再和1相加得到的结果是该数的相反数

     *

     * @param n

     * @return

     */

    public static int negNum(int n) {

        return add(~n, 1);

    }



    /**

     * 得到a-b的差

     *

     * @param a

     * @param b

     * @return

     */

    public static int minus(int a, int b) {

        //a和b的差 = a和b的相反数相加

        return add(a, negNum(b));

    }



    /**

     * a * b

     * 思路：和乘法竖式算术法计算一样

     *

     * @param a

     * @param b

     * @return

     */

    public static int multiply(int a, int b) {

        int res = 0;

        while (b != 0) {

            if ((b & 1) != 0) {  // b末尾位置不为0

                res = add(res, a);

            }

            a <<= 1;

            b >>>= 1; //无符号右移

        }

        return res;

    }



    /**

     * n是否是负数

     *

     * @param n

     * @return

     */

    public static boolean isNeg(int n) {

        return n < 0;

    }



    /**

     * a/b

     * 思路：把b往左移动到最接近a，但是不大于a时，做a = a-b，

     * 移动的位数是商的最大位置的值，然后再重新向左移动b，使得最接近a

     *

     * @param a

     * @param b

     * @return

     */

    public static int div(int a, int b) {

        int x = isNeg(a) ? negNum(a) : a;

        int y = isNeg(b) ? negNum(b) : b;

        int res = 0;

        for (int i = 31; i > -1; i = minus(i, 1)) {

            if ((x >> i) >= y) {  //x右移和y左移进行对比类似，右移比左移更安全，不会溢出

                res |= (1 << i);

                x = minus(x, y << i);

            }

        }

        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;

    }

}