package main

import (
	"math"
)

/* func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
} */

// time out
func divideOld(dividend int, divisor int) int {
	if divisor == 0 {
		return math.MaxInt32
	}
	var cnt, incr int64 = 0, 1
	if (dividend&(1<<32))^(divisor&(1<<32)) != 0 {
		incr = -1
	}
	dividend, divisor = abs(dividend), abs(divisor)
	for dividend >= divisor {
		dividend -= divisor
		cnt += incr
	}
	if cnt < math.MinInt32 || cnt > math.MaxInt32 {
		return math.MaxInt32
	}
	return int(cnt)
}

func divide(dividend int, divisor int) int {
	sign := 1
	// 判断同号、异号
	if (dividend>>31)^(divisor>>31) != 0 {
		sign = -1
	}
	dividend, divisor = abs(dividend), abs(divisor)
	res := 0
	// x/y: x -= y * 2^31, res += 2^31, x -= y * 2^30, res += 2^30, ...
	for i := uint(32); i > 0; i-- {
		if divisor<<(i-1) > dividend {
			continue
		}
		dividend -= divisor << (i - 1)
		res += 1 << (i - 1)
	}
	res *= sign
	// overflow
	if res < math.MinInt32 || res > math.MaxInt32 {
		return math.MaxInt32
	}
	return res
}

/* func main() {
	fmt.Println(divide(-1, 1))
	fmt.Println(divide(-1, -1))
	fmt.Println(divide(-1<<31, -1))
	fmt.Println(divide(1, 1))
	fmt.Println(divide(535, 1))
} */