算法小记 · 不用四则运算做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 +、-、*、/ 四则运算符号。

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入为两个整数 x 和 y (1 <= m, n <= 1000000)。

输出：

对应每个测试案例，输出 x + y 的值。

样例输入：

1 2
11 18

样例输出：

3
29

首先，思考的是，不能用四则运算符，只能从别的角度来考虑。

那么，用过C语言的，自然就得考虑到C语言的优势之一 按位运算。

吾来打个样：

#include <stdio.h>
// 主要的方法是用与来求进位，用异或来求不进位的加法
unsigned int Add(unsigned int a, unsigned int b) 
{
    unsigned int sum, carry;
    
    do {
        // 按位异或运算
        sum = a ^ b;
        // 按位与运算后，再进行按位左移运算
        // << 1 相当于 *2
        carry = (a & b) << 1;
        
        a = sum;
        b = carry;
    } while (b != 0); // 对carry的值做判断，不满足条件的，则为正确的sum值
    
    return a;
}

int main(int argc, const char * argv[]) {
    unsigned int x, y;
    while (scanf("%u%u", &x, &y) != EOF) {
        printf("%u\n", Add(x, y));
    }
    return 0;
}

关于按位运算的些许补充(不了解的或遗忘了的，可以看看)：

C 语言 和其它高级语言不同的是，它完全支持 按位运算符。这与 汇编语言 的 位操作 有些相似。
因为 位运算 得到了更多的底层优化，因此同样的功能它的 效率更高。

所谓 位运算，就是对一个 比特（Bit）位 进行操作。比特（Bit） 是一个电子元器件，8 个比特 构成 一个字节（Byte），它已经是 粒度最小 的 可操作单元 了。

// C语言中提供的六种按位运算符
& 位逻辑与
| 位逻辑或
^ 位逻辑异或
~ 位逻辑反
>> 右移
<< 左移

标准的 C 语言其实并不支持二进制数字，只不过有些编译器自己进行了扩展，才支持二进制数字。换句话讲就是，并非所有的编译器都支持二进制数字，只有一部分编译器支持，并且跟编译器的版本还有关系。

C 语言中不能直接使用 二进制 数字，按位运算符 两边的操作数可以是十进制、八进制、十六进制，因为它们在内存中最终皆是以 二进制 的形式存储，按位运算符就是对这些 内存中 的 二进制位 进行运算。其他的位运算符也是相同的道理。

提醒：按位运算符 是根据内存中的二进制位进行运算的，而不是数据的二进制形式；其他位运算符也一样。

按位与运算 (&)

    /*
     * 按位与运算 (&)
     * 一个比特（Bit）位只有 0 和 1 两个取值，只有参与 & 运算的两个位都为 1 时，结果才为 1，否则为 0。
     * 例如：1 & 1为 1，0 & 0为 0，1 & 0也为 0，这和逻辑运算符 && 非常类似。
     * 
     *   0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0010  //表示十进制的 2 (在内存中的的存储)
     * & 0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0001  //表示十进制的 1 (在内存中的的存储)
     * ---------------------------------------------------
     *   0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0000  //表示十进制的 0 (在内存中的的存储)
     *
     */
    int m = 2;
    int n = 1;
    printf("%d \n", (m & n));  //输出为 0

按位或运算 (|)

    /*
     * 按位或运算 (|)
     * 一个比特（Bit）位只有 0 和 1 两个取值，只要参与 | 运算的两个二进制位有一个为 1 时，结果就为 1，两个都为 0 时结果才为 0。
     * 例如：1 | 1为 1，0 | 0为 0，1 | 0为 1，这和逻辑运算中的||非常类似。
     *
     *   0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0010  //表示十进制的 2 (在内存中的的存储)
     * | 0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0001  //表示十进制的 1 (在内存中的的存储)
     * ---------------------------------------------------
     *   0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0011  //表示十进制的 3 (在内存中的的存储)
     *
     */
    int m = 2;
    int n = 1;
    printf("%d\n", (m | n));  //输出为 3

按位异或运算 (^)

    /*
     * 按位异或运算（^）
     * 一个比特（Bit）位只有 0 和 1 两个取值，只要当参与 ^ 运算两个二进制位不同时，结果就为 1，相同时结果则为 0。
     * 例如：0 ^ 1为 1，0 ^ 0为 0，1 ^ 1为 0。
     * 
     *   0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0010  //表示十进制的 2 (在内存中的的存储)
     * ^ 0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0001  //表示十进制的 1 (在内存中的的存储)
     * ---------------------------------------------------
     *   0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0011  //表示十进制的 3 (在内存中的的存储)
     *    
     */
    int m = 2;
    int n = 1;
    printf("%d\n", (m ^ n));  //输出为 3

取反运算 (~)

    /*
     * 取反运算（~）
     * 一个比特（Bit）位只有 0 和 1 两个取值，取反运算符~为单目运算符，右结合性，作用是对参与运算的二进制位取反。
     * 例如：~1为 0，~0为 1，这和逻辑运算中的!非常类似。
     * ~ 0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0001  //表示十进制的 1 (在内存中的的存储)
     * ---------------------------------------------------
     *   1111 1111 -- 1111 1111 -- 1111 1111 -- 1111 1110  //表示十进制的 -2 (在内存中的的存储)
     * 在计算机中，负数以原码的补码形式表达。
     * 正数的补码与原码相同，负数的补码为对该数的原码(除符号位外)逐位取反，然后在最后一位加 1。
     * 二进制中，如果有符号， 最高位表示符号, 0 为正, 1 为负,
     * -2 的二进制原码是：1000 0000 -- 0000 0000 -- 0000 0000 - 0000 0010
     * -2 的二进制补码是：1111 1111 -- 1111 1111 -- 1111 1111 - 1111 1101
     * -2 的o二进制补码加1 是：1111 1111 -- 1111 1111 -- 1111 1111 -- 1111 1110
     */
    int n = 1;
    printf("%d\n", (~ n));  //输出为 -2

左移运算 (<<)

    /*
     * 左移运算 (<<)
     * 一个比特（Bit）位只有 0 和 1 两个取值，左移运算符<< 就是把操作数的各个二进制位全部左移若干位，高位丢弃，低位补 0。
     *
     * << 0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0001  //表示十进制的 1 (在内存中的的存储)
     * ---------------------------------------------------
     *    0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 1000  //表示十进制的 8 (在内存中的的存储)
     *
     */
    int n = 1;
    printf("%d\n", (n << 3));  //输出为 8

右移运算（>>）

    /*
     * 右移运算 (>>)
     * 一个比特（Bit）位只有 0 和 1 两个取值，右移运算符>> 就是把操作数的各个二进制位全部右移若干位，低位丢弃，高位补 0 或 1。
     * 如果数据的最高位是 0，那么就补 0；如果最高位是 1，那么就补 1。
     *
     * >> 0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0001  //表示十进制的 1 (在内存中的的存储)
     * ---------------------------------------------------
     *    0000 0000 -- 0000 0000 -- 0000 0000 -- 0000 0000  //表示十进制的 0 (在内存中的的存储)
     *
     */
    int n = 1;
    printf("%d\n", (n >> 3));  //输出为 0