[algorithm] sword finger offer2 golang interview question 1: integer division

[ Algorithm ] The finger of the sword offer2 golang Interview questions 1： Integer division

subject 1:

Given two integers a and b , Find the quotient of their division a/b , It is required that the multiplication sign... Shall not be used ‘*’、 devide ‘/’ And the remainder symbol ‘%’ .

Be careful ：

The result of integer division should be truncated （truncate） Its decimal part , for example ：truncate(8.345) = 8 as well as truncate(-2.7335) = -2
Suppose our environment can only store 32 Bit signed integer , The value range is [−231, 231−1]. In this question , If the division result overflows , Then return to 231 − 1

 Example  1：

 Input ：a = 15, b = 2
 Output ：7
 explain ：15/2 = truncate(7.5) = 7
 Example  2：

 Input ：a = 7, b = -3
 Output ：-2
 explain ：7/-3 = truncate(-2.33333..) = -2
 Example  3：

 Input ：a = 0, b = 1
 Output ：0
 Example  4：

 Input ：a = 1, b = 1
 Output ：1
 

 Tips :

-231 <= a, b <= 231 - 1
b != 0

Ideas 1:

The first idea is to use speech instead of division

such as 5/2 Can keep 5-2=3> 0; res ++;
3-2=1 > 0; res++

But encountered 100000/2 It's too complicated , We try to use exponential increments , such as 5/2

15 - 2 = 13> 2; res = 1
15- 4 = 11> 2 ; res = 2
15- 8 > 7 >2; res = 4
15 - 16 = -1 < 2; res = 8, This value gives up , res = 4, And add... To the total return value 4, resTotal += res, Union divisor =7, From the beginning, the index increases
7-2 = 5 > 2 ; res = 1
7-4 = 3 > 2 ; res = 2
7 -8 = -1 < 2; res =4, This value gives up , res = 2, And add... To the total return value 2, …

func myDividefunc(a int, b int) int {
    
	// The return value will overflow  +2^32
	// Wrong input :  Divisor is 0
	if (a == math.MinInt32 && b == -1) || b == 0 {
    
		return math.MaxInt32
	}
	// The recording time is positive 
	negative := 2
	if a > 0 {
    
		negative--
		a = -a
	}
	if b > 0 {
    
		negative--
		b = -b
	}
	//  Negative number calculation result 
	res := divideCore(a, b)
	if negative == 1 {
    
		res = -res
	}
	return res
}
func divideCore(a int, b int) int {
    
	res := 0
	// -7 <= -3
	for a <= b {
    
		resAdd := 1
		b2 := b
		for {
    
			// Double every time 
			if a < (b2 + b2) {
    
				// The result doubled each time 
				resAdd += resAdd
				b2 += b2
			} else {
    
				break
			}
		}
		a -= b2
		res += resAdd
	}
	return res
}

Code

func divide(a int, b int) int {
    
	// The return value will overflow  +2^32
	// Wrong input :  Divisor is 0
	if (a == math.MinInt32 && b == -1) || b == 0 {
    
		return math.MaxInt32
	}
	// The recording time is positive 
	negative := 2
	if a > 0 {
    
		negative--
		a = -a
	}
	if b > 0 {
    
		negative--
		b = -b
	}
	//  Negative number calculation result 
	res := divideCore(a, b)
	if negative == 1 {
    
		res = -res
	}
	return res
}

//-7/-3
// Calculate in exponential increments 
//-7 < -3, 1
//-7 < -6 2
// -7 > -12 3
//-13/3
func divideCore(a int, b int) int {
    
	res := 0
	// -7 <= -3
	for a <= b {
    
		resAdd := 1
		b2 := b
		for {
    
			// Double every time 
			if a < (b2+b2) {
    
				// The result doubled each time 
				resAdd += resAdd
				b2 += b2
			}else {
    
				break
			}
		}
		a -= b2
		res += resAdd
	}
	return res
}

test