LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 既然不能用乘除法和求余，自然就会想到位运算。除法的本质就是被除数一直减去除数，直到不够减为止，减的次数就是商

100 / 3

3 * 2 ^ 1 = 6
3 * 2 ^ 2 = 12
3 * 2 ^ 3 = 24
3 * 2 ^ 4 = 48
3 * 2 ^ 5 = 96
3 * 2 ^ 6 > 100
100 - 3 左移 5 次 = 4 => 继续求 4 / 3

3 * 2 ^ 1 > 4
4 - 3 左移 0 次 = 1 < 3 => 结束计算

左移 5 次和左移 0 次 => 结果为 2 ^ 5 + 2 ^ 0 = 33

• 该过程代码如下

int x = 被除数;
int y = 除数;

int res = 0;
while (x >= y) {
  int t = y;
  int cnt = 0;  // 记录左移次数
  while (x >= t + t) {
    t <<= 1;  // t = t + t
    ++cnt;
  }
  x -= t;

  int toAdd = 1;
  while (cnt--) toAdd <<= 1;
  res += toAdd;
}

• 上述逻辑可合并为

while (x >= y) {
  int t = y;
  int cnt = 1;
  while (x >= t + t) {
    t <<= 1;  // t = t + t
    cnt <<= 1;
  }
  x -= t;
  res += cnt;
}

• 上面考虑的是两个正数相除，此外还应该考虑异号相除的情况。这种情况只要先把两个数都转为正数计算即可，如果两个数异号，计算完成后对结果取负即可。用异或可以方便地判断两个数是否异号

// 异或的本质是两个数如果不同，则返回 true
if (x != y) ...
// 等价于
if (x ^ y) ...

// 因为数在计算机中用二进制表示，最高位是符号位
// 正数最高位为 0，负数为 1，两者异或结果为 1，仍为负数
if ((x > 0 && y < 0) || (x < 0 && y > 0)) ...
// 可简化为
if ((x ^ y) < 0) ... // 注意加括号，^ 优先级低于 <

• 最后还要考虑溢出，将 int 换为 long 即可，此外该题有一个特殊用例需要单独处理

-2147483648 / -1 = 2147483647
// 即
INT_MIN / -1 = INT_MAX

• 最终完整解法如下

class Solution {
 public:
  int divide(int dividend, int divisor) {
    if (dividend == 0) {
      return 0;
    }
    if (dividend == INT_MIN && divisor == -1) {
      return INT_MAX;
    }
    long x = labs(dividend);
    long y = labs(divisor);
    long res = 0;
    while (x >= y) {
      long t = y;
      long cnt = 1;
      while (x >= t + t) {
        t <<= 1;
        cnt <<= 1;
      }
      res += cnt;
      x -= t;
    }
    return (dividend ^ divisor) < 0 ? -res : res;
  }
};