关注互联网应用及运维技术的个人博客

Golang实现进制计算两种方法

本文将以二进制计算作为例子实现

给定两个二进制字符串,返回他们的和(用二进制表示)。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

逐位计算

解法一:逐位计算

func addBinary(a string, b string) string {
    m, n := len(a), len(b)
    if m > n {
        return addBinary(b, a)
    }

    buf := make([]byte, n+1)
    carry := 0
    // 从后往前依次算尾数结果
    for i, j := n-1, m-1; i >= 0; i-- {
        if j >= 0 {
            carry += int(a[j] - '0')
            j--
        }
        carry += int(b[i] - '0')
        // 判断进位
        buf[i+1] = byte(carry%2 + '0')
        carry /= 2
    }
    // 判断是否有进位
    if carry == 0 {
        return string(buf[1:])
    }
    buf[0] = '1'
    return string(buf)
}

位运算

首先计算两个数字的无进位相加结果和进位,然后计算无进位相加结果与进位之和。同理求和问题又可以转换成上一步,直到进位为 0 结束。

计算

  • 把 aa 和 bb 转换成整型数字 xx 和 yy,xx 保存结果,yy 保存进位。
  • 当进位不为 0:y != 0:
    • 计算当前 xx 和 yy 的无进位相加结果:answer = x^y。
    • 计算当前 xx 和 yy 的进位:carry = (x & y) << 1。
    • 完成本次循环,更新 x = answer,y = carry。
  • 返回 xx 的二进制形式。

位运算

运用支持库 math/big ,里面的大数计算

func addBinary(a string, b string) string {
    x, _ := new(big.Int).SetString(a, 2)
    y, _ := new(big.Int).SetString(b, 2)
    zero, _ := new(big.Int).SetString("0", 2)

    // 
    for y.Cmp(zero) != 0 {
        answer  := new(big.Int).Xor(x, y)
        carry := x.And(x, y).Lsh(x, 1)
        x, y = answer, carry
    }
    return fmt.Sprintf("%b", x)
}
赞(0)
未经允许不得转载:飞天狒狒 » Golang实现进制计算两种方法

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址