( z5 _# k/ M  Y

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

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. // 递归写法  
   - w: x3 e5 C& W. L% s" z$ Z* S( S
2. int add(int num1, int num2){
   $ j0 G2 i% f) }% {4 g) p( z, `
3. if(num2 == 0)
   
4. return num1;
   
5. int sum = num1 ^ num2;
   1 L! S! C+ F2 T7 M
6. int carry = (num1 & num2) << 1;
   
7. return add(sum, carry);
   % u: J  i; A5 R% Y7 r% P" {3 o9 a
8. }
   3 ~5 N' a3 R3 r0 R; d" k
9. 
   
10. // 迭代写法  
    / A& j+ e3 V3 f
11. int add(int num1, int num2){
    0 c/ z; j/ x1 \( @
12. int sum = num1 ^ num2;
    0 p- D6 x& |1 Y% B9 h. b$ C5 p' b
13. int carry = (num1 & num2) << 1;   
    
14. while(carry != 0){
    & N4 D9 V1 L3 t0 L
15. int a = sum;
    6 Z% g5 y0 b) }' M* Q! d9 U
16. int b = carry;  
    
17.         sum = a ^ b;
    $ u+ V: t8 Z, L% d0 f
18.         carry = (a & b) << 1;  
    $ ~! B- d; @+ Z' q
19.     }
    
20. return sum;
    : x! K' q7 n4 ?& o  k
21. }

复制代码

1 U. q" W6 g  P, H2 E

文章出处： STM32嵌入式开发