这个题目在今年初，我的一个同事去面试的时候遇到过，回来一直给我吐槽，我又不是面试的算法工程师，问的些啥问题呀？哈哈~
我相信很多人，如果没有经常学习的话，多半也会一脸懵逼，我也是其中一个:)。虽然这些问题在实际工作用能用上的机会很少，但是对于我们拓展思维，以及了解语言底层的一些逻辑运算，还是非常有帮助的。

题目描述：

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数
dividend 除以除数 divisor 得到的商。

说明:

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

举个实际例子，57/4，实际需要的商为14，余数为1。
一个比较容易想到的办法是直接用减法，使用57-4=53，而53>4；再用53-4=49一次类推，直到减出来的差值<4，而此时做减法的次数，就是我们需要的商值。这个办法很实在，最大的问题就在于效率。57这个数比较很小，如果是999999/4呢，哪这个循环次数或者递归次数就比较难受了。

参考网上大神的解法，采用位运算。
这种运算方式在我们实际开发中用的比较少，所以也不太容易想得到，但是提起来，就是，哦哦哦哦哦，我知道我知道。。。
先来看一下代码：

package com.leetcode.learning;

public class _0029Division {
    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;
      //用异或来计算是否符号相异
        negative = (dividend ^ divisor) <0;
        long t = Math.abs((long) dividend);
        long d= Math.abs((long) divisor);
        int result = 0;
        for (int i=31; i>=0;i--) {
        	//找出足够大的数2^n*divisor
            if ((t>>i)>=d) {
            	//将结果加上2^n
                result+=1<<i;
              //将被除数减去2^n*divisor
                t-=d<<i;
            }
        }
        //符号相异取反
        return negative ? -result : result;
    }
}

比较难理解的部分其实在于循环体内部，我们还是以57/4为例好了。
先将被除数做一个位运算，右移的位数从31循环到0,57>>31剩下的就只有一串0了，肯定比除数还小，不行不行，继续循环，让右移的位数减少，直到数字3出现，57>>3=7，7>=4符合要求；然后被除数替换为57-4 * 2³=25，除数不变，还是4，结果从0变成2³=8；再继续25>>2=6，6>=4符合要求；继续将被除数替换为25 - 4 * 2²= 9，除数不变，还是4，结果从8变成8+2²=12；再继续9>>1=4，4>=4符合要求；被除数替换为9 - 4 * 2¹=1，除数不变，还是4，结果从12变成12+2¹=14；再循环1>>0=1 ,1>=0不符合要求
所以最终商为14。
会不会觉得直接从代码的运算逻辑去思考，还是觉得有些不理解？
试着从商的角度去理解，被除数，除数，余数，商，任何一个商值都可以有限不重复的2ⁿ值相加来表示，比如上面的14，可以表示为2+4+8=2¹ + 2² + 2³ = 14；换个100/3的例子，商为33，余数为1，商其实可以表示为1+32=2¹ + 2⁵ =33，if判断语句中，(t>>i)>=d其实就是判断的就是该被除数是不是含有除数多个2ⁱ ，如果有，则结果累加2ⁱ，被除数也需要减去这一坨；如果没有，则判断有没有更小的2ⁱ，依次类推，知道循环到1为止。