【logisim】如何不用加号实现加法函数——低级版

大家好，借着如何不用加号实现加法的由头，前阵子已经写过这些了：

为了阅读代码,可以运用IDEA自带的重构技巧, 把代码的不同形式进行转换.

J K L，公众号：K字的研究【预热】如何不用加号实现加法函数?
减治特点则是每次规模减少的是个常数,比如这里每次少1.

J K L，公众号：K字的研究【详解】如何不用加号实现加法函数？

不过感觉,这个话题能写的还没写完,今天继续.

还是研究这个问题，不用上次的excel了, 这次换了个工具。至于什么工具,暂时保密.

上篇回顾

前面一篇得到两个东西：

与，a&b 计算进位 C(arry)
异或， a^b 计算当前位的和 S(um)

这里我们引入一个限制,入参限制为只能是1或0, 借助一个Pair作为返回值同时返回C和S，可以得到这样一个函数:

Pair<Integer, Integer> halfAdd(int a, int b) {
    return Pair.of(a&b, a^b);
}

这个函数的入参只有4种情况,真值表如下:

0  0 (0,0)
0  1 (0,1)
1  0 (0,1)
1  1 (1,0)

在这种真值表下, 这个函数,其实相当于一个半加器(Half Adder).

半加器

半加器的功能是, 输入两个bit,产生一个和S,一个进位C.

这东西一般是拿来组电路用的,逻辑电路如下:

为什么这个东西叫半加呢?因为他不是全家.

全加器(Full adder)

半加器的入参是两个, 全加器除了这两个, 还需要考虑低位进位值Cin,一共是3个入参,出参还是两个.为了区分记为Cout和S.

逻辑电路图如下,红框里是上面的半加器,整个橙色的构成全加器.

全加器的3入2出写成对应函数的形式是:

Pair<Integer, Integer> fullAdd(int a, int b, int c) {
        var v = halfAdd(a, b);
        var lc = v.getLeft();
        var ls = v.getRight();
        return Pair.of((c & ls) | lc, ls ^ c);
}

多位加法器

现在这个全加器只支持1个bit的加法, 如果要支持多位,比如4位,8位,32位的加法, 可以采用串联或者并联.

串联比较简单,大概下图这样,构成了一个4位全加器. 画面大小有限, 换了一个原生组件.那个正方形框代表全加器,3入2出的接口没变. 我们把上一个全加器的cout连到下一个全加器的cin上去.

一共是4个加法器串联起来
左边红框里是4个输入bit
中间红框是另一个4bit输入
最右侧是输出结果.
低位在上面

加法函数写法

当然, 这个4位加法器也是可以用程序模拟的.

 int add(int a, int b) {
        int n = 4;
        int carry = 0;
        int result = 0;

        for (int i = 0; i < n; i++) {
            int an = (a >> i) & 1;
            int bn = (b >> i) & 1;
            
            var v = fullAdd(an, bn, carry);
            
            carry = v.getLeft();
            int s = v.getRight();
            
            result |= s << i;
        }
        return result;
 }

利用第0篇提到过的劣化代码技巧, 这个代码可以改成这个样子.

    static int add(int a, int b) {
        int carryIn = 0;
        int sum = 0;

        for (int i = 0; i < 32; i++) {
            var carrayOut = (carryIn & ((a >> i) & 1 ^ (b >> i) & 1)) | (a >> i) & 1 & ((b >> i) & 1);
            sum |= ((a >> i) & 1 ^ (b >> i) & 1 ^ carryIn) << i;
            carryIn = carrayOut;
        }
        return sum;
    }