! ]7 a# F# H6 Q2 K3 T$ n

    有如下十进制的加法运算：

13 + 9 = 22

    我们像这样来拆分这个运算过程：

※       不考虑进位，分别对各位数进行相加，结果为sum：个位数3加上9为2；十位数1加上0为1；最终结果为12；

※       只考虑进位，结果为carry：3 + 9 有进位，进位的值为10；

※       如果步骤2所得进位结果carry不为0，对步骤1所得sum，步骤2所得carry重复步骤1、 2、3；如果carry为0则结束，最终结果为步骤1所得sum：这里即是对sum = 12和carry = 10重复以上三个步骤，(a) 不考虑进位，分别对各位数进行相加:sum = 22; (b) 只考虑进位: 上一步没有进位，所以carry = 0；(c) 步骤2carry= 0，结束，结果为sum = 22。

    把上面的运算过程放在二进制中试试。

   13和9的二进制分别为：

0000 1101

0000 1001

    ①不考虑进位，分别对各位数进行相加得到sum：‍

0000 0100

    ②当考虑进位，有两处进位，第0位和第3位，只考虑进位的结果为carry：

0001 0010

    ③判断carry是否为0，为0则结束，最终计算结果为sum;如果carry不为0，则进行如下操作，并重复步骤①②③：

sum+=carry

    上面步骤③中判断carry不为0，回到步骤①：

    不考虑进位，sum+carry= ：

0001 0110

    步骤②：

    只考虑进位，carry =：

0

    步骤③：

    判断carry为0，结束，最终sum=:

0001 0110

    转换成十进制刚好是22，十进制的算法同样适用于二进制！

    仔细观察发现：

第①步不考虑进位的加法其实就是异或运算

第②步只考虑进位就是按位与运算之后左移一位

第③步就是重复前面两步操作，直到第二步进位结果为0

    这里为什么要循环步骤①②③，直到步骤②所得进位carry等于0呢？这是因为有的数做加法时会出现连续进位的情况。在第③步检测carry如果为0，则表示没有进位了，此时，此次循环第①步的sum即为最终的结果。

通过位运算实现加法

按照上面的分析，写出通过位运算实现加法的如下代码：

1. // 递归写法  
   
2. int add(int num1, int num2){
   
3. if(num2 == 0)
   
4. return num1;
   
5. int sum = num1 ^ num2;
   7 C6 \; l. W! Y
6. int carry = (num1 & num2) << 1;
   ( k& W9 }; w# _# E( m
7. return add(sum, carry);
   9 h& E, Y+ a+ m/ F
8. }
   
9. 
   
10. // 迭代写法  
    
11. int add(int num1, int num2){
    / r. @9 `& A3 P$ f# U
12. int sum = num1 ^ num2;
    
13. int carry = (num1 & num2) << 1;   
    
14. while(carry != 0){
    
15. int a = sum;
    
16. int b = carry;  
    - n3 Y* d0 m& H) ~/ ^) c
17.         sum = a ^ b;
    
18.         carry = (a & b) << 1;  
    ) G; f* p6 }; u$ Y* g5 Q; h, b
19.     }
    
20. return sum;
    
21. }

复制代码

! ^9 P3 O4 \4 c+ b5 Z9 I+ `0 V

文章出处： STM32嵌入式开发

# _5 w, t8 i  h- z" H