Go 语言实现经典 Ripple Adder 涟波加法器算法

3. 全加器（Full Adder）

功能：

• 处理：A、B、Cin（输入进位）

逻辑表达式：

Sum = A XOR B XOR Cin Carry = (A AND B) OR (Cin AND (A XOR B))

4. 涟波加法器结构

• 多个全加器串联
• 前一位的 Carry 输出 → 下一位的 Carry 输入
• 延迟与位数线性相关

实现思路

Ripple Adder 的实现流程如下：

步骤一：定义半加器

用于构建全加器的基础模块。

步骤二：定义全加器

• 使用两个半加器
• 合并进位信号

步骤三：构建涟波结构

• 从最低位开始
• 顺序传播进位
• 逐位计算结果

步骤四：输出最终结果

• 得到完整和
• 得到最终溢出位

完整实现代码

// =======================================================
// 文件名：ripple_adder.go
// 功能：经典 Ripple Adder（涟波加法器）算法实现
// =======================================================
package main

import (
	"errors"
	"fmt"
)

// -------------------------------
// 半加器（Half Adder）
// -------------------------------
func HalfAdder(a, b int) (sum, carry int) {
	sum = a ^ b // XOR
	carry = a & b // AND
	return
}

// -------------------------------
// 全加器（Full Adder）
// -------------------------------
func FullAdder(a, b, cin int) (sum, carry int) {
	// 第一个半加器
	s1, c1 := HalfAdder(a, b)
	// 第二个半加器
	sum, c2 := HalfAdder(s1, cin)
	// 合并进位
	carry = c1 | c2
	return
}

// -------------------------------
// Ripple Adder（涟波加法器）
// -------------------------------
func RippleAdder(a, b []int) ([]int, int, error) {
	if len(a) != len(b) {
		return nil, 0, errors.New("binary inputs must have the same length")
	}
	n := len(a)
	result := make([]int, n)
	carry := 0

	// 从最低位开始逐位相加
	for i := n - 1; i >= 0; i-- {
		result[i], carry = FullAdder(a[i], b[i], carry)
	}
	return result, carry, nil
}

func main() {
	// 示例输入（二进制）
	a := []int{1, 0, 1, 1} // 11
	b := []int{0, 1, 1, 0} // 6
	sum, carry, err := RippleAdder(a, b)
	if err != nil {
		fmt.Println("Error:", err)
		return
	}
	fmt.Println("A =", a)
	fmt.Println("B =", b)
	fmt.Println("SUM =", sum)
	fmt.Println("CARRY =", carry)
}

代码解读

1. HalfAdder

实现最基本的两位相加逻辑，输出和与进位。

2. FullAdder

在半加器基础上引入输入进位，实现完整单比特加法。

3. RippleAdder

通过串联多个全加器，模拟进位从低位到高位逐级传播的过程。

4. main

用于验证算法正确性，展示完整加法流程。

总结

通过本项目，我们完成了：

1. 从逻辑门到多位加法器的完整构建
2. 进位传播机制的直观模拟
3. 硬件加法器结构的软件复现
4. 理解 CPU 算术单元的基础工作方式

一句话总结：

Ripple Adder 是'最慢的加法器'，但也是'最重要的教学加法器'

常见问题

Q1：为什么 Ripple Adder 慢？

因为进位必须一位一位传播。

Q2：为什么还要学它？

因为所有高速加法器都是在'解决它的问题'。

Q3：真实 CPU 用这个吗？

现代 CPU 用改进型，但原理完全继承。

Q4：下一步该学什么？

Carry Lookahead Adder。

扩展方向

1. Carry Lookahead Adder（超前进位）
2. Carry Save Adder
3. ALU 设计
4. 补码加减法
5. 从加法器到 CPU 执行单元