不用加减乘除做加法

2020-12-24

剑指 Offer 65. 不用加减乘除做加法

难度简单121

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

示例:

1 2	输入: a = 1, b = 1 输出: 2

提示：

a, b 均可能是负数或 0
结果不会溢出 32 位整数

位运算

无进位和与异或运算规律相同，计算和（不考虑进位时）使用异或运算

进位的规律和与运算的规律相同，计算进位时使用与运算

class Solution {
    public int add(int a, int b) {
        int sum = 0, carry = 0;
        do {
            sum = a ^ b;            //二进制加法中，两数相加，如果相同位的数字相同为0，不同为1
            carry = (a & b) << 1;   //某一位都是1，那么有进位，进位要左移一位（也就是进到更高的那一位）

            a = sum;                //然后让原先的结果再和进位做加法，查看是否还有新的进位
            b = carry;

        } while (b != 0);           //如果没有新的进位，加法执行完成
        
        return a;
    }
}

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true