# LeetCode 29: Divide Two Integers 解析
>quoted from `zjupure`'s [LeetCode solution](https://leetcode.com/problems/divide-two-integers/discuss/13420/32-times-bit-shift-operation-in-C-with-O(1)-solution):
## Problem

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part.
For example, `truncate(8.345) = 8` and `truncate(-2.7335) = -2`.
**Example 1**:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

**Example 2**:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

**Note**:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31^, 2^31^ − 1]. For the purpose of this problem, assume that **your function returns 2^31^-1 when the division result overflows.**
Solution

## [AlvinZH 的解析 (C++ code)](https://www.cnblogs.com/AlvinZH/p/8643676.html)

>本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

舉例來說

$40 \div 3$

可以看成是

40 個積木 (Dividend)，每 3 個一組 (Divisor)的話總共可以分成幾組 (Quotient)？又剩下幾個湊不成一組的積木 (Remainder)？

最直觀的方法是：
:::success

**Step1 : 減去一整組積木的數量**
* 每次把剩下的積木減去一整組的數量 1 * 3 (共有一組，每組有3個)，看還有多少積木剩下來

**Step2 : 比較 Remainder 與 Divisor的大小**
* 如果剩下來的積木數量大於等於 $1\times 3$ (Divisor) 的話
* 就把剩下的積木數量 assign 給新的 Dividend
* 回到步驟 1
* 如果剩下來的積木數量小於 $1\times 3$ (Divisor) 的話
* 代表現在得到的組數就是最後的 Quotient
* 剩下來湊不滿 3 個的數量，就是最後的 Remainder
* 跳出迴圈，告訴使用者最後的 Quotient
:::

運作 2 個回合來觀察

* Round 1
* 40 (Dividend) - 1 * 3 (Divisor) = 37 (Remainder)
* 因為 37 (Remainder) > 1 * 3 (Divisor)
* 把 remainder 37 當做新的 Dividend
* 回到步驟 1
* (此時 Dividend 為 37, Divisor 仍是 1 * 3)
* Round 2
* 37 (Dividend) - 1 * 3 (Divisor) = 34 (Remainder)
* 因為 34 (Remainder) > 1 * 3 (Divisor)
* 把 remainder 34 當做新的 Dividend
* 回到步驟 1
* (此時 Dividend 為 34, Divisor 仍是 1 * 3)
* Round 13
* 4 (Dividend) - 1 * 3 (Divisor) = 1
* 因為 1 (Remainder) < 1 * 3 (Divisor)
* 所以 最後 Remainder 為 1
* 一共減了 13 次，
* 代表 40 可以分成 13 組積木(每組有3個積木)
* 所以 Quotient 是 13
* 剩下 1 個湊不滿一組的積木
* 所以 Remainder 是 1
* 結束

## 改進版的演算法 - 每次減去 2^n^ 個 3，剪完後 n = n + 1

* 因為一次減去一組太慢了，所以改成
* Round 1
* $40 - 2^{0} \times 3 = 37$
* Round 2
* $37 - 2^{1} \times 3 = 34$

\begin{eqnarray}
40 &=& 1 \times 2^{0} \times 3+\
0 \times 2^{1} \times 3 +\
1 \times 2^{2} \times 3 +\
1 \times 2^{3} \times 3\\
&=& 3 + 12 + 24
\end{eqnarray}

:::danger
如何決定什麼時候不減去那個冪值 ?
e.g. $2^1 \times 3$ 的那一組
原來我搞錯用法了，dividend 在內層回圈永遠不變，而是把 divisor 每次乘以 2
:::

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        long dvd = labs(dividend), dvs = labs(divisor), ans = 0;
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
        while (dvd >= dvs) {
            long temp = dvs, cnt = 1;
            while (temp << 1 <= dvd) {
                temp <<= 1;
                cnt <<= 1;
            }
            dvd -= temp;
            ans += cnt;
        }
        return sign * ans;
    }
};

分析:
assume

* dvd 是 `15`
* dvs 是 `3`
* 因為在 line 9 如果能夠進入迴圈代表 dvd 至少會是 1 倍的 dvs,
* 所以我們設 `cnt = 1`
* temp 存放著這回合內有幾組積木(每 `dvs` 個為一組)
* `temp` 的數值:
* $2^{n} \times dvs$, n starts from 0
* `m` 代表當下一共累積了幾個 `dvs`

* :question: `m` 的用途是？
* 計算line 9 的 while loop 這一輪一共減去了多少個 `dvs`
* Counter 的概念
* :question: `temp` 的用意是？
* 第 n 回合時 $temp = cnt \times dvs$
* $cnt = 2^{n}$ n 為 內層回圈經過的回合數
* 存放我們要與 dvd 比較的數值，也就是一共減去了多少個 `dvs`

* 當 $temp == cnt \times 3$ 比 dvd 大時，代表我們這一輪已經減去最大的 dvs 倍數了
* e.g. 40 - 8 * 3 =
* 此時就把剩下來的餘數變成 `dvd`, 再重新開始用 temp 去減他

| Round (outer loop) | Round(inner loop) | temp (after that round) | dvd | dvs | cnt | | |
|--------------------|-------------------|------------------------------|-----|-----|-----|---|---|
| R0 (init) | R0(init) | $2^{0} \times 3$ | 40 | 3 | $2^0$ | | |
| | R1 | $2^{1} \times 3$ | 40 | 3 | $2^1$ | | |
| | R2 | $2^{2} \times 3$ | 40 | 3 | $2^2$ | | |
| | R3 | $2^{3} \times 3$ | 40 | 3 | $2^3$ | | |
| | R4 | x, because (temp << 1) > dvd | x | x | x | | |
| | | | | | | | |

----

先嘗試做出一個一個減的方法，

int divide(int dividend, int divisor){
     if(divisor == 0 || (dividend == INT_MIN && divisor == -1)) {
            return INT_MAX;
    }
    long dvd = labs(dividend);
    long dvs = labs(divisor);
    int count = 0;
    int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
    while (dvd >= dvs) {
        dvd -= dvs;
        count += 1;
    }
    return sign * count;
}

Leetcode 出現問題

Line 11: Char 15: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int' (solution.c)

:::success
TODO: 解釋為什麼 count 會 integer overflow
TODO: 解釋為什麼 這個 [submission](https://leetcode.com/submissions/detail/403321452/) 會出現

Runtime Error Message:
Line 7: Char 39: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.c)

Last executed input:
-2147483648
1

因為 signed integer 是 4 個 bytes,
數值範圍是
[INT_MIN, INT_MAX] = [$-2^{31}, 2^{31}-1$]
而 INT_MIN 取絕對值的數值是 $2^{31}$，超出了 signed int 的表示範圍，所以會出錯
適當的做法是，使用 long 來保存這個取絕對值後的數值，而不是 signed int
這也是為什麼 `INT_MIN` 要用以下方法定義

#  define INT_MIN   (-INT_MAX - 1)  
#  define INT_MAX   2147483647

>## 7.18 Integer types <stdint.h>

TODO: 查看 32 bit 64 - bit 架構 int, long int 的數值範圍
[Stack Overflow: Why do we define INT_MIN as -INT_MAX - 1? [duplicate]](https://stackoverflow.com/questions/26003893/why-do-we-define-int-min-as-int-max-1)
TODO: measure time in linux
:::

## abs(INT_MIN) 的問題

* :question: 以下使用 abs 取絕對值的方法有什麼問題呢？

long dvd = (long) abs(dividend);
long dvs = (long) abs(divisor);

* Ans:
:::spoiler
in manpage
>NOTES
>Trying to take the absolute value of the most negative integer is not defined.

所以以下的寫法在 `abs` 的 argument 是 `INT_MIN` 時會出現 Undefined behavior

    long dvd = (long) abs(dividend);
    long dvs = (long) abs(divisor);

應改成

         /* Cast to long integer for computing */
    -    long dvd = (long) abs(dividend);
    -    long dvs = (long) abs(divisor);
    +    long dvd = (long) labs((long) dividend);
    +    long dvs = (long) labs((long) divisor);

:::

## temp integer overflow 問題

在 dividend == INT_MIN, divisor == 1 時，temp 與 count 的數值都會超過 integer 能表達的上限，所以
* temp 型態改成 long
* :question: temp 改成 unsigned int 會有什麼問題？
:::spoiler

* 不使用 unsigned int 的原因是，因為他要做 `temp << 1` 的位移，在 `temp == INT_MAX + 1`，也就是 `2147483648` 時，下一輪 `temp << 1` 會變成 0，造成無窮迴圈

            temp: (unsigned int)
            0x80    0x00    0x00    0x00

            temp << 1: (cause infinite loop)
            0x00    0x00    0x00    0x00

:::
* 把 count 型態改成 unsigned int
* 把 ans 型態改成 unsigned int
* sign 維持不變 (因為他有可能是 -1, 不能使用 unsigned int 表示)

@@ -58,16 +58,16 @@ int divide(int dividend, int divisor)
 #endif
     /* Construct for answer */
     int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
-    int ans = 0;
+    unsigned int ans = 0;
     while (dvd >= dvs) {
-        int temp = dvs;
-        int count = 1;
+        long temp = dvs;
+        unsigned int count = 1;
         while ((temp << 1) <= dvd) {
             temp <<= 1;
             count <<= 1;
         }
 #if DEBUG_ON
 

## Type conversion (補充)
>In c99 - Def of integer promotion
> # 6.3 Conversions
> If an int can represent all values of the original type, the value is converted to an int;
otherwise, it is converted to an unsigned int. These are called the integer
promotions.48) All other types are unchanged by the integer promotions.
* [INT02-C. Understand integer conversion rules
](https://wiki.sei.cmu.edu/confluence/display/c/INT02-C.+Understand+integer+conversion+rules)

### Test for converting integer to long integer
> test at Little_Endian machine x86-64 machine

1	#include <limits.h>
2	#include <stdio.h>
3
4
5	int main()
6	{
7	    int i = INT_MIN;
8	    long l = (long)i;
9	    return 0;
10	}

gdb test

(gdb) l
1	#include <limits.h>
2	#include <stdio.h>
3
4
5	int main()
6	{
7	    int i = INT_MIN;
8	    long l = (long)i;
9	    return 0;
10	}
(gdb) b 8
Breakpoint 1 at 0x605: file int_to_long.c, line 8.
(gdb) n
The program is not being run.
(gdb) r
Starting program: /home/ubuntu/linux2020/sandbox/type_casting/int_to_long

Breakpoint 1, main () at int_to_long.c:8
8	    long l = (long)i;
(gdb) p i
$1 = -2147483648
(gdb) x/8xb &i
0x7fffffffe3b4:	0x00	0x00	0x00	0x80	0x00	0x00	0x00	0x00
(gdb) n
9	    return 0;
(gdb) x/8xb &k
No symbol "k" in current context.
(gdb) x/8xb &l
0x7fffffffe3b8:	0x00	0x00	0x00	0x80	0xff	0xff	0xff	0xff

可以看到 line 7 我們 assign i 的 value 為 INT_MIN
他的 binary representation 是

0x00	0x00	0x00	0x80
convert to big endian: 
0x80    0x00    0x00    0x00 

當 cast 成 long integer 並 assign 給 l 時，integer 會被 cast 成 long integer，並用 extend signe bit 的方法產生

0x00	0x00	0x00	0x80	0xff	0xff	0xff	0xff

convert to big endian:

0xff	0xff	0xff	0xff    0x80    0x00	0x00	0x00

如何做 integer promotion?
> 就是 CS:APP 的 extended signed bit

## Why this [FAIL](https://leetcode.com/submissions/detail/407584864/):
* 沒考慮到 `INT_MIN` divided by -1
* result 會 overflow
*

============================ TEST 2 =======================
test case: dvd =     -2147483648, dvs =              -1
FAIL
expected :           -2147483647
get                  -2147483648

After fixed:

============================ TEST 2 =======================
test case: dvd =     -2147483648, dvs =              -1
PASS
test case: dvd =     -2147483648, dvs =              -1
result: 2147483647

## 其實內部運算不該用 long int!
>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, assume that your function returns 2^31^ − 1 when the division result overflows.
:::success
TODO: Try not to use long
>Ref: [C++ bit manipulations](https://leetcode.com/problems/divide-two-integers/discuss/13407/C%2B%2B-bit-manipulations)
:::

### Debug lee215's ans

int divide(int A, int B)
{
    if (A == INT_MIN && B == -1)
        return INT_MAX;
    int a = abs(A), b = abs(B), res = 0;
    for (int x = 31; x >= 0; x--)
        if ((signed) ((unsigned) a >> x) - b >= 0)
            res += 1 << x, a -= b << x;
    return (A > 0) == (B > 0) ? res : -res;
}

output:

============================ TEST 1 =======================
test case: dvd =     -2147483648, dvs =               1
divid_int.c:45:9: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself
divid_int.c:48:22: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'
divid_int.c:48:35: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'
divid_int.c:49:37: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself

#### fixed: [Deal with the edge condition when input is INT_MIN](https://github.com/unknowntpo/sandbox/commit/518c06f4acb7c77313f9870d054b20012d97b448)

>Deal with the edge condition when input is INT_MIN
>
>Suppose we take absolute of signed integer x, abs(x)
when x is INT_MIN, the result is undefined,
but when x is INT_MIN, the absolute value of x is simply equals to
(unsigned) x,
so we take this property, and carefully transfer x to its absolute
value.

>With this patch, the runtime error is gone.

divid_int.c:45:9: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself

diff --git a/leetcode/29_Divide_Two_Integers/divid_int.c b/leetcode/29_Divide_Two_Integers/divid_int.c
index 73e78ab..41a9057 100644
--- a/leetcode/29_Divide_Two_Integers/divid_int.c
+++ b/leetcode/29_Divide_Two_Integers/divid_int.c
@@ -42,7 +42,11 @@ int divide(int A, int B)
 {
     if (A == INT_MIN && B == -1)
         return INT_MAX;
-    int a = abs(A), b = abs(B), res = 0;
+
+    /* Take abs of a and b, dealed with boundary condition */
+    int a = (A == INT_MIN) ? (unsigned) A : abs(A);
+    int b = (B == INT_MIN) ? (unsigned) B : abs(B);
+    unsigned int res = 0;
     for (int x = 31; x >= 0; x--)
         if ((signed) ((unsigned) a >> x) - b >= 0)
             res += 1 << x, a -= b << x;

### Leetcode29 in go
* :question: What's the diff between nested loop ver. and loop - if version
* :question: dvd - dvs << i == dvd >> i - dvs?
* :question: Diff between this code

for dvd >= dvs {
        temp = dvs
        cnt = 1
        for dvd >= (temp << 1) {
                temp <<= 1
                cnt <<= 1
        }
        dvd -= temp
        ans += cnt
}

以下方法成立是因為 dvd 可以向右移動的次數與 dvs 向左移動相同

e.g. 40 / 3

dvd right shift
40 - 2^0 * 3 = 37   (i == 0)
40 - 2^1 * 3 = 34
40 - 2^2 * 3 = 28
40 - 2^3 * 3 = 16  (i == 3)

dvs left shift

40 / 2^0 - 3 = 37  (i == 0)
40 / 2^1 - 3 = 17
40 / 2^2 - 3 = 7
40 / 2^3 - 3 = 2   (i == 3)
40 / 2^4 - 3 <0 (if 條件不成立)

## :question: 每次 left shift dvs 行為 為什麼不需要 nested loop ?

// Left shift dividend
for i := 31; i >= 0; i-- {
        if (dvd >> i) >= dvs {
                ans += 1 << i
                dvd -= (1 << i) * dvs
        }
}

// right shift divisor
// ? Why got -ans?
var power2 uint = 0
	for i := 31; i >= 0; i-- {
        if dvd>= (dvs << i) {
            power2 = 1 << i 
			ans += power2
			dvd -= power2 * dvs
		}
	}

Nested loop ver.

for dvd >= dvs {
        temp = dvs
        cnt = 1
        for dvd >= (temp << 1) {
                temp <<= 1
                cnt <<= 1
        }
        dvd -= temp
        ans += cnt
}