题目

leecode 371两整数之和
给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和

原理

要实现基本运算, 有没有想过这些运算是如何在计算机底层实现的?
从半加器开始，逐步介绍计算机如何执行加法和其他数学运算。

逻辑门

逻辑门是集成电路的基本组件。简单逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”（T；true）与“假”（F；false）或二进制的1和0，从而实现逻辑运算。常见的逻辑门包括与门，或门，非门，异或门（也称互斥或）。

AND(与门)

全入皆高才出高。
一低出低。

A B 输出
0 0 0
0 1 0
1 0 0
1 1 1

OR(或门)

全入皆低才出低。

A B 输出
0 0 0
0 1 1
1 0 1
1 1 1

XOR(异或)

只有其中一项输入为高，输出为高；否则出低。

A B 输出
0 0 0
0 1 1
1 0 1
1 1 0

半加器

半加器就像在玩乐高积木一样，我们开始用最基本的积木组合成更大的结构。半加器是这个“积木世界”的第一个积木，让我们一起来了解它。

想象你有两个小朋友，每个小朋友手里拿着一个玩具球，一个是0，一个是1。半加器的工作就像是让这两个小朋友把玩具球放到一起，然后告诉你他们手里玩具球的数量。如果两个小朋友手里都是0，告诉你的结果是0；如果有一个小朋友手里是1，结果就是1；如果两个小朋友手里都是1，那结果就是10，也就是二进制的2。

这种“两个小朋友”和“玩具球”的组合就是半加器。它接受两个二进制数字作为输入，并产生两个输出：一个是当前位的和，另一个是进位（如果有的话）。

总而言之，半加器是一个非常基础、简单的电路，用于执行二进制数字的最基本加法运算。就像玩积木一样，我们会继续搭建更多的结构，使计算机能够做更复杂的事情。

半加器电路图

输入包括两个位：A 和 B。
输出包括：

  • 和（sum）：A XOR(异或) B，这表示两个输入位相加的结果。
  • 进位（carry）：A AND(与) B，这表示两个输入位相加时产生的进位。

例如

假设我们要计算 3 + 2（以二进制表示为 0011 + 0010），我们可以使用两个半加器来执行这个操作，每个半加器负责一个位的加法。
首先，我们将 3 和 2 的二进制位输入到两个半加器：
半加器 1
输入： A = 1, B = 0
输出： Sum = 1, Carry = 0
半加器 2
输入： A = 1, B = 1
输出： Sum = 0, Carry = 1

现在，我们可以将这两个半加器的 Sum 输出连接在一起，得到结果：

半加器 1

1
2
3
4
  1
+ 0
-------
  1

半加器 2 产生了一个进位（Carry = 1），我们需要将这个进位加到最终结果中。因此，最终结果是：

1
2
3
4
  0
+ 0
-------
  0

1(carry)0(sum)1(sum)
🤔单个半加器会得到当前位的sum 及进位carry, 如何添加进位计算得到最终的结果呢?
👉 全加器可以帮我们解决

全加器

在一个半加器的下, 我们能得出两位的和跟进位, 那么可能用两个半加器从而实现一个全加器。方法是将它们连接起来，其中一个半加器处理两个输入位（A 和 B），而另一个半加器处理一个输入位（Cin）和前一个半加器的进位输出（carry）。这种组合使得第一个半加器计算出两个输入位的和和进位，第二个半加器将这个进位与第三个输入位相加，得到最终的和和进位，从而实现了一个完整的三位全加器的功能。

全加器电路图

输入包括三个位：A、B 和进位输入（Cin）。
输出包括：

  • 和（sum）：(A XOR B) XOR Cin，这表示三个输入位相加的结果。
  • 进位（carry）：(A AND B) OR (Cin AND (A XOR B))，这表示三个输入位相加时产生的进位。

例如

用全加器来解释上面半加器的例子 3+2
3 的二进制表示为 0011
2 的二进制表示为 0010
n表示A/B/C的第n位

最低位:

输入： A_0 = 1, B_0 = 0, C_in = 0
半加器 1
输出: Sum_0 = 1, Carry_out_1 = 0

半加器 2
输出: Sum_0 = 1, Carry_out_2 = 0

进位传递到下一位。

次低位:

输入： A_1 = 1, B_1 = 1, C_in = Carry_out_2 = 0 (上一位的进位)
半加器 1
输出: Sum_1 = 0, Carry_out_1 = 1
半加器 2
输出: Sum_1 = 0, Carry_out_2 = 1

进位传递到下一位。

次高位:

输入： A_2 = 0, B_2 = 0, C_in = Carry_out_2 = 1 (上一位的进位)
半加器 1
输出: Sum_2 = 0, Carry_out_1 = 0
半加器 2
输出: Sum_2 = 1, Carry_out_2 = 0

进位传递到下一位

最高位:

输入： A_3 = 0, B_3 = 0, C_in = Carry_out_2 = 0 (上一位的进位)
半加器 1
输出: Sum_3 = 0, Carry_out_1 = 0
半加器 2
输出: Sum_3 = 0, Carry_out_2 = 0

最终的结果为：
Sum = 0101（二进制，即十进制的 5）

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fn main() {
    let a = 13;
    let b = 21;
    println!("结果{}", get_sum(a, b));
}

fn get_sum(a: i32, b:i32) -> i32 {
    // 获取进位
    let mut carry = a & b;
    // 获取和sum
    let sum = a ^ b;
    let mut result: i32 = sum;

    while carry != 0 {
      result = result + (carry << 1);
      carry = sum & carry;
    }
    return result;
}