# Question

Formatted question description: https://leetcode.ca/all/29.html

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.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

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:

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

# Algorithm

To perform Bit Manipulation, you can utilize another artifact bit. The algorithm operates as follows:

1. Check if the dividend is greater than or equal to the divisor. If it is, initialize a variable t to be equal to the divisor and a count variable p to 1.
2. While twice t is less than or equal to the dividend, double t, double p, and update the result.
3. Continue the above step until t is greater than the dividend.
4. Determine the sign of the result based on the signs of the dividend and divisor. Use a long integer type for calculations and multiply the result by the sign.
5. Handle special cases like when the divisor is 0 or the dividend is -2147483648 and the divisor is -1. For such cases, return INT_MAX.

# Code

• 
/*
* converting int to larger size type like long, or BigInteger.
* since overflow on -2147483648 must be handled
*/
public class Divide_Two_Integers {

public static void main(String[] args) {
Divide_Two_Integers out = new Divide_Two_Integers();
Solution_recursion s = out.new Solution_recursion();

System.out.println(s.divide(101, 10));
System.out.println(s.divide(-2147483648, 2));
}

// @note: give up on bit operation, biggest issue is, bit and negative int are hard to handle
public class Solution_bit_on_int {
public int divide(int n, int dsor) {
if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
return Integer.MAX_VALUE;
}

// save operations
if(dsor == 1) {
return n;
}
if(dsor == -1) {
return n * -1;
}

int flag = 1;
if(n < 0) {
flag *= -1;
n *= -1; // @note: overflow... -2147483648/2
}
if(dsor < 0) {
flag *= -1;
dsor *= -1;
}

int count = 0;
// while(n > 0) {
//     n -= dsor;
//     count++;
// }

// moving faster than above while
while(n > 0 && n >= dsor) { // while(n > 0) { @note: I missed case: 1/2
int shift = 0; // bit shift

/* @note: below bit operation causes issue.
2147483647/1
last loop, shift=31, dsor=1
should not enter below while, but when divisor is 1 or 2 or 4, etc:

1<<31=(-2147483648)
2<<30=(-2147483648)
4<<29=(-2147483648)

so, originally I was using "(dsor << shift)" as probe to see if over divident
then I change it to be an int, and add extra overflow check
*/

// while((dsor << shift) <= n) {
while((dsor << shift) <= n) { //@note: <n is non-stop loop, should be <=n. eg. 1/1
n -= dsor << shift;
count += 1 << shift;

// check bit overflow
if((Integer.MAX_VALUE >> 1) <= (dsor << shift)) {
break;
}

shift++;
}
}

return count * flag;
}
}

public class Solution_recursion {

int result = 0;
/*
* my way of acceleration, increase step size each iteration,
*
* eg:
*
* 101 / 10:
* 		101 - 10*1 = 91
* 		91 - 10*2 = 71
* 		71 - 10*4 = 31
*
* now 31 is less then 10*8, count=1+2+4=7 ok, send to next recursion
*
* 31 / 10: and repeat above acceleration, start again from step=1
* 		31 - 10*1 = 21
* 		21 - 10*2 = 1
*
* now 1 is less than 10*4, this recurion count=1+2=3
*
*/
public int divide(int dividend, int divisor) {

// convert to long
long n = (long)dividend;
long dsor = (long)divisor;

if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
return Integer.MAX_VALUE;
}

// save operations
if(dsor == 1) {
return (int)n;
}
if(dsor == -1) {
return (int)(n * -1);
}

int flag = 1;
if(n < 0) {
flag *= -1;
n *= -1; // @note: overflow... -2147483648
}
if(dsor < 0) {
flag *= -1;
dsor *= -1;
}

dfs(n, dsor);

return flag * result;
}

public void dfs(long n, long dsor) {

//	    	if(n <= 0) {
if(n < dsor) { // @note: missed here, end condition is not n
return;
}

int step = 1;

while (n >= (dsor * step)) { // @Note: should be >= , eg: 2/2 = 1

n -= (dsor * step);

result += step;

step *= 2; // acceleration of step size
}

// now start again with no acceleration dsor
dfs(n, dsor);
}
}

// @note: just convert to long, and solution AC. But code is ugly...
public class Solution {
public int divide(int nn, int ddsor) {

// convert to long
long n = (long)nn;
long dsor = (long)ddsor;

if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
return Integer.MAX_VALUE;
}

// save operations
if(dsor == 1) {
return (int)n;
}
if(dsor == -1) {
return (int)(n * -1);
}

int flag = 1;
if(n < 0) {
flag *= -1;
n *= -1; // @note: overflow... -2147483648
}
if(dsor < 0) {
flag *= -1;
dsor *= -1;
}

int count = 0;
// while(n > 0) {
//     n -= dsor;
//     count++;
// }

// moving faster than above while
while(n > 0 && n >= dsor) { // while(n > 0) { @note: I missed case: 1/2
int shift = 0; // bit shift

/* @note: below bit operation causes issue.
2147483647/1
last loop, shift=31, dsor=1
should not enter below while, but when divisor is 1 or 2 or 4, etc:

1<<31=(-2147483648)
2<<30=(-2147483648)
4<<29=(-2147483648)

so, originally I was using "(dsor << shift)" as probe to see if over divident
then I change it to be an int, and add extra overflow check
*/

// while((dsor << shift) <= n) {
while((dsor << shift) <= n) { //@note: <n is non-stop loop, should be <=n. eg. 1/1
n -= dsor << shift;
count += 1 << shift;

// check bit overflow
if((Integer.MAX_VALUE >> 1) <= (dsor << shift)) {
break;
}

shift++;
}
}

long result = count * flag;
if(result > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
} else if(result < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
} else {
return (int)result;
}

}
}

public class Solution_over_time_limit {
public int divide(int n, int dsor) {
if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) {
return Integer.MAX_VALUE;
}

int flag = 1;
if(n < 0) {
flag *= -1;
n *= -1;
}
if(dsor < 0) {
flag *= -1;
dsor *= -1;
}

int count = 0;
while(n > 0) {
n -= dsor;
count++;
}

return count * flag;
}
}

}

############

class Solution {
public int divide(int a, int b) {
int sign = 1;
if ((a < 0) != (b < 0)) {
sign = -1;
}
long x = Math.abs((long) a);
long y = Math.abs((long) b);
long tot = 0;
while (x >= y) {
int cnt = 0;
while (x >= (y << (cnt + 1))) {
cnt++;
}
tot += 1L << cnt;
x -= y << cnt;
}
long ans = sign * tot;
if (ans >= Integer.MIN_VALUE && ans <= Integer.MAX_VALUE) {
return (int) ans;
}
return Integer.MAX_VALUE;
}
}

• // OJ: https://leetcode.com/problems/divide-two-integers/
// Time: O(logD) where D is |dividend|
// Space: O(1)
class Solution {
public:
int divide(int dividend, int divisor) {
if (!divisor) return 0;  // divide-by-zero error
bool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2);
if (pos1) dividend = -dividend;
if (pos2) divisor = -divisor;
int q = 0, d = divisor, t = 1;
while (t > 0 && dividend < 0) {
if (dividend - d <= 0) {
dividend -= d;
q -= t;
if ((INT_MIN >> 1) < d) {
t <<= 1;
d <<= 1;
}
} else {
d >>= 1;
t >>= 1;
}
}
return pos? -q : q;
}
};

• class Solution:
def divide(self, a: int, b: int) -> int:
INT_MAX = (1 << 31) - 1
INT_MIN = -(1 << 31)
sign = -1 if a * b < 0 else 1
a = abs(a)
b = abs(b)
tot = 0
while a >= b:
cnt = 0
while a >= (b << (cnt + 1)):
cnt += 1
tot += 1 << cnt
a -= b << cnt
return sign * tot if INT_MIN <= sign * tot <= INT_MAX else INT_MAX

############

class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
if divisor == 0:
return 0x7fffffff
sign = 1
if dividend * divisor < 0:
sign = -1
ans = 0
cnt = 1
dividend = abs(dividend)
divisor = abs(divisor)
subsum = divisor
while dividend >= divisor:
while (subsum << 1) <= dividend:
cnt <<= 1
subsum <<= 1
ans += cnt
cnt = 1
dividend -= subsum
subsum = divisor
return max(min(sign * ans, 0x7fffffff), -2147483648)


• func divide(a int, b int) int {
sign, ans, INT32_MAX, INT32_MIN, LIMIT := false, 0, 1<<31-1, -1<<31, -1<<31/2
if (a > 0 && b < 0) || (a < 0 && b > 0) {
sign = true
}
a, b = convert(a), convert(b)
for a <= b {
cnt := 0
// (b<<cnt) >= LIMIT 是为了避免 b<<(cnt+1) 发生溢出
for (b<<cnt) >= LIMIT && a <= (b<<(cnt+1)) {
cnt++
}
ans = ans + -1<<cnt
a = a - b<<cnt
}
if sign {
return ans
}
if ans == INT32_MIN {
return INT32_MAX
}
return -ans
}

func convert(v int) int {
if v > 0 {
return -v
}
return v
}


• public class Solution {
public int Divide(int dividend, int divisor) {
return (int)DivideInternal(dividend, divisor);
}

public long GetHighestBit(long x)
{
if (x == 0) return 0;
long k = 0x80000000;
while ((x & k) == 0)
{
k >>= 1;
}
return k;
}

public long DivideInternal(long dividend, long divisor)
{
int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
if (dividend < 0) dividend = -dividend;
if (divisor < 0) divisor = -divisor;

long result = 0;
long pointer = GetHighestBit(dividend);
dividend = dividend ^ pointer;
while (pointer > 0)
{
result <<= 1;
{
++result;
}
pointer >>= 1;
bool nextIsOne = (dividend & pointer) != 0;
dividend = dividend ^ (nextIsOne ? pointer : 0);
}

result = sign * result;

if (result > int.MaxValue || result < int.MinValue)
{
return int.MaxValue;
}
return result;
}
}