#yyds干货盘点# LeetCode程序员面试金典：两数相除

　　题目：

　　给你两个整数，被除数pidend和除数pisor。相除两个数字，要求 不使用 乘法、除法和取余操作。

　　整数除法应向零截断，即截断(truncate)小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

　　除以除数pisor获得的返回被除数pidend 商 。

　　注：假设我们的环境只能储存 32 位 有符号整数，其数值范围为 [−231, 231− 1] 。在这个问题中，如果是商人 严格大于 231− 1 ，则返回 231− 1 ;如果商 严格小于 -231 ，则返回 -231 。

　　示例1:

　　输入: pidend = 10, pisor = 3

　　输出: 3

　　解释: 10/3 = 3.33333.. ，零截断后得到 3 。

　　示例2:

　　输入: pidend = 7, pisor = -3

　　输出: -2

　　解释: 7/-3 = -2.33333.. ，零截断后得到 -2 。

　　代码实现：class Solution { public int pide(int pidend, int pisor) { // 考虑被除数为最小值的情况 if (pidend == Integer.MIN_VALUE) { if (pisor == 1) { return Integer.MIN_VALUE; } if (pisor == -1) { return Integer.MAX_VALUE; } } // 考虑最小除数值的情况 if (pisor == Integer.MIN_VALUE) { return pidend == Integer.MIN_VALUE ? 1 : 0; } // 考虑被除数为 0 的情况 if (pidend == 0) { return 0; } // 一般情况下，用二分搜索 // 将所有正数取相反数，这只需要考虑一种情况 boolean rev = false; if (pidend > 0) { pidend = -pidend; rev = !rev; } if (pisor > 0) { pisor = -pisor; rev = !rev; } int left = 1, right = Integer.MAX_VALUE, ans = 0; while (left <= right) { // 注意溢出，除法不能使用 int mid = left + ((right - left) >> 1); boolean check = quickAdd(pisor, mid, pidend); if (check) { ans = mid; // 注意溢出 if (mid == Integer.MAX_VALUE) { break; } left = mid + 1; } else { right = mid - 1; } } return rev ? -ans : ans; } // 快速乘 public 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; }}