题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例一：

1
2
3

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例二：

1
2
3

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

题解

位运算

首先想到的是对被除数循环递减, 记录能减多少次就好了, 但是明显效率太低.

那么这个循环递减的过程就可以使用移位运算优化一下.计算机在做移位时效率很高, 向左移1位相当于乘以2, 向右移1位相当于除以2

设循环初始值为i = 31, 每次循环都比较dividend>>i 和 devisor的大小, 起初结果肯定是小于关系. 一旦变成了等于或大于关系, 则说明商至少是2^i

以100除以3为例说明:

i从31, 30, …,开始循环, 当i=5时, 有(100>>5)>=3, 即100/32>=3, 说明100中至少有32个3, 然后让余数4继续完成遍历.

这样的方法最多只只需要遍历31个数字即可.

public int divide(int dividend, int divisor) {

        if (dividend == 0)
            return 0;
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;

        boolean negative = (dividend ^ divisor) < 0;
        long t = Math.abs((long) dividend);
        long d = Math.abs((long) divisor);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            if ((t >> i) >= d) {
                res += 1 << i;
                t -= d << i;
            }
        }
        return negative ? -res : res;
    }