binary - 作为二元运算的加法

Question

我正在添加一对无符号 32 位二进制整数（包括溢出）。加法是表达性的，而不是实际计算的，因此不需要有效的算法，但是由于每个组件都是根据单个位手动指定的，因此我需要一个具有紧凑表示的组件。有什么建议么？

编辑：就布尔运算符而言。所以我carry = a & b; sum = a ^ b;首先是这么想的，但是其他 31 位呢？

哦，还有减法！

Answer 1

或许您可以先声明两个 1 位数字的加法，并带有溢出（=进位）：

A | B | SUM | CARRY
===================
0   0    0      0
0   1    1      0
1   0    1      0
1   1    0      1

为了进一步概括这一点，您需要一个“全加器”，它也将前一阶段的进位作为输入。然后，您可以将 32 位加法表示为 32 个这样的全加器链（第一级的进位输入绑定到 0）。

Answer 2

• 关于数据结构部分来表示这些数字。有4种方式

1)Bit Array
位数组是一种紧凑地存储各个位的数组数据结构。
它们也称为位图、位集或位串。

2)Bit Field
位域是计算机编程中常用的习惯用法，用于将多个逻辑值紧凑地存储为短系列位，其中每个位都可以单独寻址。

3)Bit Plane
数字离散信号（如图像或声音）的位平面是与表示信号的每个二进制数中的给定位位置相对应的一组位。

4)Bit Board
位板或位域是一种将一组相关的布尔变量填充到同一个整数中的格式，通常表示棋盘游戏中的位置。

• 关于实施，您可以检查在每个步骤中，我们有以下
  S = a xor b xor c

S 是当前位 a 和 b 之和的结果
c 是输入进位

Cout - 输出进位是(a & b) xor (c & (a xor b))

Answer 3

您不能使用简单的布尔运算符执行加法，您需要一个加法器。（当然，加法器可以使用一些更复杂的布尔运算符来构建。）加法器将两位加进位相加，并将进位传递给下一位。

伪代码：

carry = 0
for i = 31 to 0
  sum = a[i] + b[i] + carry
  result[i] = sum & 1
  carry = sum >> 1
next i

这是使用 VEDIT 文本编辑器的宏语言的实现。要添加的两个数字以 ASCII 字符串的形式给出，每行一个。结果插入第三行。

Reg_Empty(10)                       // result as ASCII string
#0 = 0                              // carry bit
for (#9=31; #9>=0; #9--) {
    #1 = CC(#9)-'0'                 // a bit from first number
    #2 = CC(#9+34)-'0'              // a bit from second number
    #3 = #0+#1+#2                   // add with carry
    #4 = #3 & 1                     // resulting bit
    #0 = #3 >> 1                    // new carry
    Num_Str(#4, 11, LEFT)           // convert bit to ASCII
    Reg_Set(10, @11, INSERT)        // insert bit to start of string
}
Line(2)
Reg_Ins(10) IN
Return

示例输入和输出：

00010011011111110101000111100001
00110110111010101100101101110111
01001010011010100001110101011000

编辑：
这是用布尔运算实现加法器的伪代码：

carry = 0
for i = 31 to 0
  sum[i] = a[i] ^ b[i] ^ carry
  carry = (a[i] & b[i]) | (a[i] & carry) | (b[i] & carry)
next i