首页 > 代码库 > 剑指offer (47) 不用加减乘除做加法

剑指offer (47) 不用加减乘除做加法

题目:求两个整数之和,要求不得使用 加减乘除四则运算

 

题解分析:加减乘除都不能用,还要进行各种运算,必然想到 位运算

 

十进制加法: 5 + 17 = 22

step1. 各位相加,不考虑进位,即舍弃进位,结果为 12 (5 + 7 = 12舍弃进位)

step2. 做进位 (5 + 7 = 12 > 9 有进位) 进位为10

step3. 两步结果相加 12 + 10 = 22

 

二进制加法:5 + 17 = 22 即 101 + 10001 

step1. 各位相加,不考虑进位,即舍弃进位,结果为 10100

step2. 做进位 (1 + 1 有进位) 进位为 二进制的10

step3. 10100 + 10 = 10110 = 22

 

对于二进制:

各位相加不考虑进位:0 + 0 = 0 ;1 + 1 = 0;1 + 0 = 1; 0 + 1 = 1 异或操作搞定

做进位:只有1+1才有进位,即 1&1 与操作搞定

int Add(int num1, int num2) {    int sum = 0;    int carry = 0;        do {        sum = num1 ^ num2;        carry = (num1 & num2) << 1;                num1 = sum;        num2 = carry;    } while (num2 != 0);    return num1;}