位运算-实现加、减、乘、除

2022-6-4 diaba 笔试题 

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;
    }
}

« 递归DP-机器人到达目的地方法数 | 位运算-判断数是否是2的幂、4的幂»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022