整数除法

原创

Johns

发布于 2022-09-28 14:50:31

2.8K0

文章被收录于专栏：代码工具

整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

示例 1：

输入：a = 15, b = 2

输出：7

解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3

输出：-2

解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：a = 0, b = 1

输出：0

问题分析

主要考虑如下几个问题:

被除数为0
被除数为最小值的2种情况
正负符号问题
减法效率问题

import (
	"math"
)

func divide(a int, b int) int {
	// 考虑被除数为0
	if a == 0 {
		return 0
	}

	// 考虑被除数为最小值
	if a == math.MinInt32 {
		if b == 1 {
			return math.MinInt32
		}
        if b == -1{
            return math.MaxInt32
        }
		
	}

	// flag为0或者2表示正, 否则为负
	rev := true
	if b > 0 {
		b = -b
		rev = !rev
	}
	if a > 0 {
		a = -a
		rev = !rev
	}

	count := divideCore(a, b)
	if !rev {
		return -count
	}
	return count
}

func divideCore(a, b int) int {
	count := 0
	for a <= b {
        value:=b
        quotient:=1
        for value>=math.MinInt16 && a<=(value<<1){
            quotient = quotient<<1
            value = value<<1
        }
        count+=quotient
		a -= value
	}
	return count
}

二进制加法

func addBinary(a string, b string) string {
	ans := ""
	carry := 0
	i, j := len(a)-1, len(b)-1
	for i >= 0 || j >= 0 {
		if i >= 0 {
			carry += int(a[i] - '0')
			i--
		}
		if j >= 0 {
			carry += int(b[j] - '0')
			j--
		}
		ans = strconv.Itoa(carry%2) + ans
		carry /= 2
	}
	if carry > 0 {
		ans = "1" + ans
	}
	return ans
}

整数加法

func addTen(a string, b string) string {
	ans := ""
	carry := 0
	i, j := len(a)-1, len(b)-1
	for i >= 0 || j >= 0 {
		if i >= 0 {
			carry += int(a[i] - '0')
			i--
		}
		if j >= 0 {
			carry += int(b[j] - '0')
			j--
		}
		ans = strconv.Itoa(carry%10) + ans
		carry /= 10
	}
	if carry > 0 {
		ans = "1" + ans
	}
	return ans
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

truncate