Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
func divide(dividend int, divisor int) int {
if dividend==0{
return 0
}
vice:=false
var ldividend int64=int64(dividend)
var ldivisor int64=int64(divisor)
if dividend>0{
if divisor<0{
vice=true
ldivisor=int64(0-divisor)
}
}else{
if divisor>0{
vice=true
ldividend=int64(0-dividend)
}else{
ldivisor=int64(0-divisor)
ldividend=int64(0-dividend)
}
}
var index int
index=int(f(ldividend,ldivisor))
if vice{
index=0-index
}
if index>2147483647{
index=2147483647
}
if index<=-2147483648{
index=-2147483648
}
return index
}
func index(a int64,b int64)uint64{
var i uint64 =0
for b<<i<a{
i++
}
return i
}
func f(a int64 ,b int64) int64 {
if a<b{
return 0
}
if b==1{
return a
}
if a==b {
return 1
}
var ret int64
index:=index(a,b)
tmp:=b<<index
for i:=1<<index;i>=1<<(index-1);i--{
if tmp<=a{
ret=int64(i)
break
}
tmp-=b
}
return ret
}
二分法递归,性能测试没过
var modify int
func divide(dividend int, divisor int) int {
if dividend==0{
return 0
}
vice:=false
if dividend>0{
if divisor<0{
vice=true
divisor=0-divisor
}
}else{
if divisor>0{
vice=true
dividend=0-dividend
}else{
divisor=0-divisor
dividend=0-dividend
}
}
var index int
if divisor==1{
index=dividend
}else if divisor==2{
index=f(dividend,divisor)+modify
}
if vice{
index=0-index
}
if index>2147483647{
index=2147483647
}
if index<=-2147483648{
index=-2147483648
}
return index
}
func f(a int,b int)int{
if a<b{
return 0
}
if a==b{
return 1
}
if a>>1<b{
if a>>1+a>>1-b>0{
modify=1
}
}
return f(a>>1,b)+f(a-a>>1,b)
}