整数除法

剑指offer01整数除法

题目描述

除法,不能使用/*,考虑符号.

解题思路

方法1 暴力循环 不断地减,(符号不同就加),直到换号前,返回循环次数

if a >= 0 && b > 0 {//ab大于0时
  for ; a-b >= 0; i++ {//记录循环次数
   a = a - b
  }
 } else if a > 0 && b < 0 {//a>0 , b<0
  for ; a+b >= 0; i-- {
   a = a + b
  }
 } else if a < 0 && b > 0 {//a>0 , b<0
  for ; a+b <= 0; i-- {
   a = a + b
  }
 } else {//ab小于0时
  for ; a-b <= 0; i++ {
   a = a - b
  }
 }
 if i > 2147483647 {//题目对数字极限的要求-2^31 <= a, b <= 2^31 - 1
  return 2147483647
 }
 return i

代码示例

func divide1(a int, b int) int {
 if b == 1 {//当b=1或-1时为了降低循环次数,可以直接返回
  return a
 } else if b == -1 {
  if -a > 2147483647 {
   return 2147483647
  } else {
   return -a
  }
 }
  i := 0
 if a >= 0 && b > 0 {//ab大于0时
  for ; a-b >= 0; i++ {//记录循环次数
   a = a - b
  }
 } else if a > 0 && b < 0 {
  for ; a+b >= 0; i-- {
   a = a + b
  }
 } else if a < 0 && b > 0 {
  for ; a+b <= 0; i-- {
   a = a + b
  }
 } else {
  for ; a-b <= 0; i++ {
   a = a - b
  }
 }
 if i > 2147483647 {
  return 2147483647
 }
 return i
}

但是这个提交不了,不建议使用.....原因是太过于暴力

方法2

位运算,二分查找法
二分查找可以说是最好的查找方法了

1. 首先我们考虑到a很大b很小的时候需要循环太多次,为了避免这种情况我们需要一次减b的多倍,就是运用位运算,b<<n左移n位数字扩大2^n倍也就是一次减了2^n次b,同时用一个数来记录减的次数,1<<n记录,一位一位的移动就实现了二分查找了,循环条件设置为a-b >= 0就是当a不能减b是时停止

核心算法

// 大于0时的除法
func zsc(a, b int) int {
 t := 0 //记录循环次数
 bt := b
 for i := 1; a-b >= 0; { //都大于0的情况
  if a-(bt<<1) > 0 {//如果能够继续减去左移就继续左移
   bt <<= 1
   i <<= 1
  } else {//如果不能继续减去左移就记录次数,i(临时)重新计数t(总次数)次数叠加
   a = a - bt
   t = t + i
   i = 1
   bt = b
  }
 }
 return t
}

执行结果

// 大于0时的除法
func zsc(a, b int) int {
 t := 0 //记录循环次数
 bt := b
 for i := 1; a-b >= 0; { //都大于0的情况
  if a-(bt<<1) > 0 {//如果能够继续减去左移就继续左移
   bt <<= 1
   i <<= 1
  } else {//如果不能继续减去左移就记录次数,i(临时)重新计数t(总次数)次数叠加
   a = a - bt
   t = t + i
   i = 1
   bt = b
  }
 }
 return t
}

// 返回正数
func abs(a int) int {
 if a < 0 {
  return -a
 }
 return a
}

// 位运算
func divide(a int, b int) int {
 if abs(a) < abs(b) {//比较绝对值大小,|a|<|b|返回0
  return 0
 }
 if b == 1 {//不用循环的情况
  return a
 } else if b == -1 {
  if -a > 2147483647 {
   return 2147483647
  } else {
   return -a
  }
 }
 if a >= 0 && b > 0 {//ab的各种情况全部转换正数传入计算,根据需求输出
  return zsc(a, b)//都大于0
 } else if a > 0 && b < 0 {
  return -zsc(a, -b)//a>0,b<0
 } else if a < 0 && b > 0 {
  return -zsc(-a, b)//a<0,,b>0
 } else {
  return zsc(-a, -b)//a<0..b<0
 }
}

执行用时： 4 ms , 在所有 Go 提交中击败了 47.55% 的用户 内存消耗： 2.2 MB , 在所有 Go 提交中击败了 95.10% 的用户 通过测试用例： 992 / 992