Last Updated: 2023-12-22 08:56:34 Friday
-- TOC --
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator. The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2. Return the quotient after dividing dividend by divisor.
在不使用乘法，除法和模运算的情况下，实现整数除（C语言的整数除，truncate fraction part）。
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31−1]. For this problem, if the quotient is strictly greater than 2^31-1, then return 2^31-1, and if the quotient is strictly less than -2^31, then return -2^31.
返回的quotient用32bits保存，执行饱和计算。这句话同时还约束了C/C++的方案，只能使用32bits的int类型。
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Constraints:
- -2^31 <= dividend, divisor <= 2^31-1
- divisor != 0，
不用考虑除0的情况，但可能出现最大负数除-1的情况，不过由于不允许直接只用除法运算，这个问题也就规避了。（参考：整数计算的溢出判断）
CPU就是在做加法，减法也是加法，乘法和除法，也完全可以用加法实现.....
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
neg = (dividend<0) ^ (divisor<0)
n = 0
a = abs(dividend)
b = abs(divisor)
while (a:=a-b) >= 0:
n += 1
if not neg:
return min(n,0x7FFFFFFF)
else:
return -min(n,0x80000000)
TLE!!不过，这行代码我还比较满意：neg = (dividend<0) ^ (divisor<0)，两个判断必须要括起来哈。
其实，也就比直觉算法稍微复杂了一点点，从最大的数开始做减法，这符合除法笔算思路。著名的《COD》教材中，有个硬件实现这个算法的详细描述。
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
neg = (dividend<0) ^ (divisor<0)
q = 0
a = abs(dividend)
b = abs(divisor) << 31
for _ in range(32):
r = a - b
if r >= 0:
a = r
q <<= 1
q |= 1
else:
q <<= 1
b >>= 1
if not neg:
return min(q,0x7FFFFFFF)
else:
return max(-q,-0x80000000)
由于使用了超过32bits的int，C/C++不允许使用这个算法思路。
直觉算法采用每次只减去一份的思路，速度当然慢拉。我们可以给这个思路升个级，利用左移等于乘2的原理，每次逐步减去更大的一块，这更大的一块肯定是divisor的2的幂次。当按照这个思路写代码时，感觉自然就没有必要直接使用乘法和除法了.....如果硬件平台没有除法指令可用，这是个很好的alternative。
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
positive = (dividend<0) == (divisor<0)
a = abs(dividend)
b = abs(divisor)
q = 0
while a >= b:
s = 0
while a > (b<<(s+1)):
s += 1
q += 1<<s
a -= b<<s
if q==1<<31 and positive:
return 0x7FFFFFFF
return q if positive else -q
positive = (dividend<0) == (divisor<0)，同号即为正class Solution {
public:
int divide(int dividend, int divisor) noexcept{
bool positive { (dividend<0) == (divisor<0) };
unsigned int a { static_cast<unsigned int>(abs(dividend)) };
unsigned int b { static_cast<unsigned int>(abs(divisor)) };
unsigned int q {};
while(a >= b){
unsigned int s = 0;
while((a!=b) && (a>(b<<(s+1))))
++s;
q += 1<<s;
a -= b<<s;
}
if(q==1<<31 && positive)
return INT_MAX;
return positive ? q : -q;
}
};
a!=b这个判断用来规避极端情况。abs最大负数，出现runtime error，1<<31说不能表示成一个int......anyway，C语言版本改造成如下了：
#define ABS_INT(x,y) \
do{\
int m = x>>31;\
y = ((unsigned int)(x^m))-m;\
}while(0)
int divide(int dividend, int divisor) {
bool neg = (dividend<0) != (divisor<0);
unsigned int a,b;
ABS_INT(dividend, a);
ABS_INT(divisor, b);
unsigned int q = 0;
while(a >= b){
unsigned int s = 0;
while((a!=b) && (a>(b<<(s+1))))
++s;
q += 1<<s;
a -= b<<s;
}
if((q==0x80000000) && !neg)
return INT_MAX;
return neg ? -q : q;
}
用位运算（Bit Manipulation）来实现abs功能，这也是本题的point。
本文链接：https://cs.pynote.net/ag/leetcode/202312181/
-- EOF --
-- MORE --