求解：计算两个 n 位二进制数的和时，需要遵循的循环不变性是什么？

各位小伙伴们，大家好呀！看看今天我又给各位带来了什么文章？本文标题是《求解：计算两个 n 位二进制数的和时，需要遵循的循环不变性是什么？》，很明显是关于Golang的文章哈哈哈，其中内容主要会涉及到等等，如果能帮到你，觉得很不错的话，欢迎各位多多点评和分享！

我正在解决 clrs“算法简介”中的练习 2.1-4。

问题描述为：

考虑将两个 n 位二进制整数存储在两个 n 元素数组 a 和 b 中相加的问题。这两个整数的和应以二进制形式存储在元素数组 c 中。

这个问题的循环不变量是什么？ 我对这个问题有一些想法，并将它们作为评论写在我用 golang 编写的这个问题的解决方案中。

package additoin_binary

/*
Loop invariant:
At the start of each iteration of the loop digits in the subarray r[len(r) - 1 - i:] are
a[len(a) - 1 - i:] + b[len(b) - 1 - i:] + carry | provided that (len(a) - 1 - i) and (len(b) - 1 - i) are positive
a[len(a) - 1 - i:] + carry                      | provided that (len(a) - 1 - i) is positive and (len(b) - 1 - i) is negative
carry                                           | provided that (len(a) - 1 - i) and (len(b) - 1 - i) are negative
*** carry for i = a[(len(a) - 1) - i - 1] + b[(len(b) - 1) - i - 1] == 2 ? 1 : 0
*/

func BinaryAddition(a, b []int) []int {
    // a and b can have arbitrary number of digits.
    // We should control a length of the second term. It should be less or equal to a length of first term.w
    // Other vise we swap them
    if len(b) > len(a) {
        b, a = a, b
    }
    // loop invariant initialization:
    // before first loop iteration (i=0) index b_i is out of the array range (b[-1]),  so we don't have second term and sum = a
    // another way of thinking about it is we don't get b as argument and then sum = a, too
    if len(b) == 0 {
        return a
    }
    // result array to store sum
    r := make([]int, len(a)+1)
    // overflow of summing two bits (1 + 1)
    carry := 0
    // loop invariant maintenance:
    // we have right digits (after addition) in r for indexes r[len(r) - 1 - i:]
    for i := 0; i < len(r); i++ {
        a_i := len(a) - 1 - i // index for getting a last digit of a
        b_i := len(b) - 1 - i // index for getting a last digit of b
        r_i := len(r) - 1 - i // index for getting a last digit of r

        var s int
        if b_i >= 0 && a_i >= 0 {
            s = a[a_i] + b[b_i] + carry
        } else if a_i >= 0 {
            s = a[a_i] + carry
        } else { // all indexes run out of the game (a < 0, b < 0)
            s = carry
        }

        if s > 1 {
            r[r_i] = 0
            carry = 1
        } else {
            r[r_i] = s
            carry = 0
        }
    }
    // loop invariant termination:
    // i goes from 0 to len(r) - 1, r[len(r) - 1 - ([len(r) - 1):] => r[:]
    // This means, that for every index in r we have a right sum
    //*At i=0, r[i] a sum can be equal to 0, so we explicitly check that before return r
    if r[0] == 0 {
        return r[1:]
    } else {
        return r
    }
}

编辑1：我扩展了原来的问题。所以现在数组 a 和 b 可以具有任意长度，分别为 m 和 n。示例 a = [1,0,1]，b = [1,0]（m=3，n=2）

解决方案

该问题保证 A 和 B 是 n 元素数组，我认为这是一个可以减少代码工作的重要条件。

在此问题中，如果假设 len = len(C)，则在 [0, len) 中迭代 i，循环不变式是 r[len-1-i:len] 始终是 a 的和[len-2-i:len-1] 和 b[len-2-i:len-1] 位于较低的 i + 1 位中。因为每次循环后，都会有一位正确，可以证明算法是正确的。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于Golang的相关知识，也可关注golang学习网公众号。