题目描述

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个题目要求不能用 * / % , 然后去求一个商，最暴力的想法就是去进行遍历，每一次减去一个除数，一直到被除数 小于 零 结束。

不过换一下思路，这个可以用二进制拆分的思想去解决这个问题。
我们知道，任意一个数字都可以被二进制表示，那么这个题目所求的被除数可以被几个除数表示，也同样可以进行一个二进制的拆分。
类似多重背包问题的二进制优化的思路。

首先看被除数可以表示成 2 i * 除数 + 2 j * 除数 + … … ;
然后依次求出i , j 是啥就可以了。

代码

参照大佬的实现。

class Solution {
   
public:
    int divide(int dividend, int divisor) {
   
        long ans = 0, up = fabs(dividend), down = fabs(divisor); 
        while (up > down) {
   
            int count = 1, base = down;
            while (up > (base << 1)) {
   
                count <<= 1;
                base <<= 1;
            }
            ans += count;
            up -= base;
        }
        ans = ((dividend < 0) ^ (divisor < 0)) ? -ans : ans; 
        return (ans > INT_MAX || ans < INT_MIN) ? INT_MAX : ans;
    }
};

总结

二进制拆分是很有用的一个工具，比如说用来解决这个问题。

七只老鼠，一百瓶药水，其中有一瓶是毒药，毒发时间为一天，使用一天时间检测出毒药

对100瓶毒药进行二进制编码，0000001，0000010，…，1100100

老鼠分别为A,B,C,D,E,F,G

A老鼠喝编码格式为1xxxxxx的药水

B老鼠喝编码格式为x1xxxxx的药水

C老鼠喝编码格式为xx1xxxx的药水

D老鼠喝编码格式为xxx1xxx的药水

E老鼠喝编码格式为xxxx1xx的药水

F老鼠喝编码格式为xxxxx1x的药水

G老鼠喝编码格式为xxxxxx1的药水

最后查看老鼠死亡情况，假如C和D死亡，说明0011000为毒药。

神奇。