《C语言入门100例》(第1例) A+B

【第01题】A + B | 基础输入输出，开启学习C语言打卡的序章

• • • 1. Leetcode 371. 两整数之和
    • • 题目描述
      • 初见
      • 思路
      • 代码
    • 2. Leetcode 面试题 08.05. 递归乘法
    • • 题目描述
      • 初见
      • 思路
      • 代码

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

不用加号与减号的情况下，就是直接计算二进制加法，int 为 32 字节，因此对每一位进行一次二进制计算即可。此时代码如下：

int getSum(int a, int b) {
    int result(0), add1(0);
    for (int i = 0; i < 32; ++i) {
        char curBitA = a >> i & 0x1;
        char curBitB = b >> i & 0x1;
        // 计算当前位结果并更新 result
        int curBit = curBitA ^ curBitB;
        if (add1) {
            result = result | (!curBit << i);
        } else {
            result = result | (curBit << i);
        }
        // 更新是否进位
        if ((curBitA && curBitB) || ((curBitA || curBitB) && add1)) {
            add1 = 1;
        } else {
            add1 = 0;
        }
    }
    return result;
}

那么，有没有更简洁的方法呢？

使用 ^ 可以完成二进制中不进位的加法运算，那么只要找到表示进位的方法就能完成整个加法运算过程。
进位运算只在两数的二进制表示相同位置均为 1 时发生，用 & 可找到待进位的位置，此时将 & 运算结果左移 1 位即完成进位操作。使用相同方法将进位结果与不进位结果相加，直至不再需要进位操作。

1. C = A ^ B 得到按位加的结果;
2. D = A & B << 1 得到进位后的结果;
3. 若 D != 0 则令 A = C, B = D，重复步骤 1, 2;
   若 D == 0 则返回 C ^ D.

int getSum(int a, int b) {
    int result(0);
    do {
        result = a ^ b;
        b = (unsigned int)(a & b) << 1;
        if (b == 0) {
            result = result ^ b;
            break;
        } else {
            a = result;
        }
    } while (b != 0);
    return result;
}

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

不用乘运算符，那么只要使用迭代加法即可。此时代码如下：

int multiply(int A, int B) {
    if (B == 0) {
        return 0;
    }
    return A + multiply(A, B - 1);
}

如此暴力的解法竟然没有超时，看来是测试用例不行啊。

对于乘法使用加法进行拆分是自然的想法，那么位移可以做什么呢？当然是 × 2 times2 ×2 啦！分奇偶情况进行拆分：
a × 2 n = 2 a × n ; a × ( 2 n + 1 ) = a + a × 2 n a times 2n = 2a times n; \ a times (2n + 1) = a + a times 2n a×2n=2a×n;a×(2n+1)=a+a×2n
将上述乘法换为位移操作：

1. 找出 A 与 B 中较小元素 a = m i n ( A , B ) a = min(A, B) a=min(A,B) 与较大元素 b = m a x ( A , B ) b = max(A, B) b=max(A,B)，使用 a a a 对 b b b 进行迭代以减少迭代次数;
2. 若 a = = 1 a == 1 a==1, 则返回 b b b;
   若 a = = 2 a == 2 a==2, 则返回 b < < 1 b << 1 b<<1;
3. 若 a % 2 = = 0 a % 2 == 0 a%2==0 则令 r e s u l t = b < < 1 result = b << 1 result=b<<1, 并使用步骤 1 - 4 计算 r e s u l t × a / 2 result times a / 2 result×a/2 的结果;
   若 a % 2 = = 1 a % 2 == 1 a%2==1 则令 r e s u l t = b result = b result=b, 并使用步骤 1 - 4 计算 r e s u l t + r e s u l t × ( a − 1 ) result + result times (a - 1) result+result×(a−1) 的结果.

int multiply(int A, int B) {
    int result(0);
    int maxNum = A > B? A: B;
    int minNum = A <= B? A: B;
    // 用 minNum 对 maxNum 进行循环，减少循环次数
    if (minNum == 1) {
        return maxNum;
    } else if (minNum == 2) {
        return maxNum << 1;
    } else if (minNum % 2 == 0) { // a * 2n = 2a * n
        result = maxNum << 1;
        return multiply(result, minNum / 2);
    } else if (minNum % 2 == 1) { // a * (2n + 1) = a + a * 2n
        result += maxNum;
        return result + multiply(result, minNum - 1);
    } else {
        return result;
    }
}