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

Categories:

题目描述
思路分析
1. 解法一：位运算模拟加法（推荐）
相似题目

题目描述

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

思路分析

解法一：位运算模拟加法（推荐）

核心思路：

a ^ b 得到不考虑进位的和。

(a & b) << 1 得到进位。

迭代直到进位为 0。

复杂度分析：

时间复杂度：O(1)，整数位数固定。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            // 无进位和
            int sum = a ^ b;
            // 进位
            int carry = (a & b) << 1;

            a = sum;
            b = carry;
        }

        return a;
    }
}

func add(a int, b int) int {
    for b != 0 {
        // 无进位和
        sum := a ^ b
        // 进位
        carry := (a & b) << 1

        a = sum
        b = carry
    }

    return a
}

相似题目

题目	难度	考察点
371. 两整数之和	中等	位运算
190. 颠倒二进制位	简单	位运算
191. 位1的个数	简单	位运算
136. 只出现一次的数字	简单	位运算
338. 比特位计数	中等	动态规划、位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/44537108