两数相除
题目形容：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不应用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 失去的商。
整数除法的后果该当截去（truncate）其小数局部，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：二分查找
首先，判断几种非凡的状况； 而后用二分查找法找到除数。
解法参考的leetcode官网的解法。
public class LeetCode_029 { /** * 二分查找 * * @param dividend 被除数 * @param divisor 除数 * @return */ public static int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE) { if (divisor == 1) { // 当被除数为最小值，除数为1时，间接返回最小值 return Integer.MIN_VALUE; } if (divisor == -1) { // 当被除数为最小值，除数为-1时，相除会溢出，间接返回最大值 return Integer.MAX_VALUE; } } if (dividend == 0) { // 如果被除数为0，除以任何数都为0，间接返回0 return 0; } if (divisor == Integer.MIN_VALUE) { if (dividend == Integer.MIN_VALUE) { // 如果被除数和除数都是最小值，返回1 return 1; } else { // 当除数是最小值，被除数不是最小值时，相除的后果必定是在-1和1之间，返回0 return 0; } } // 将所有的负数取相反数，这样就只须要思考一种状况 boolean rev = false; if (dividend > 0) { dividend = -dividend; rev = !rev; } if (divisor > 0) { divisor = -divisor; rev = !rev; } int left = 1, right = Integer.MAX_VALUE, ans = 0; while (left <= right) { // 留神溢出，并且不能应用除法 int mid = left + ((right - left) >> 1); boolean check = quickAdd(divisor, mid, dividend); if (check) { ans = mid; // 留神溢出 if (mid == Integer.MAX_VALUE) { break; } left = mid + 1; } else { right = mid - 1; } } return rev ? -ans : ans; } /** * 疾速乘 * * @param y * @param z * @param x * @return */ public static boolean quickAdd(int y, int z, int x) { // x和y是正数，z是负数 // 须要判断 z*y >= x 是否成立 int result = 0, add = y; while (z != 0) { if ((z & 1) != 0) { // 须要保障 result + add >= x if (result < x - add) { return false; } result += add; } if (z != 1) { // 须要保障 add + add >= x if (add < x - add) { return false; } add += add; } // 不能应用除法 z >>= 1; } return true; } public static void main(String[] args) { System.out.println(Integer.toBinaryString(10)); System.out.println(Integer.toBinaryString(6)); System.out.println(Integer.toBinaryString(3)); System.out.println(divide(10, 3)); }}【每日寄语】 以淡泊的模样，经验烟雨尘风的袭击，还原初时的本人。轻拥欢笑，时光深处，温顺静坐。