LeetCode 面试题 17.01. 不用加号的加法

2023-12-13 16:30:50

一、题目

??设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

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

提示:

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

??点击此处跳转题目

二、C# 题解

??将 a、b 进行二进制加法,ai、bi 表示 a、b 第 i 位的值(0或1),ci 表示第 i 位的进位(0或1)。使用 ans 表示计算结果,初始情况 ans 各位均为 0。

  1. ci = 0
    • ai = bi:ai、bi 不是 0 就是 1,因此相加后该位结果均为 0,ans 不做处理
      • ai = bi = 0,则计算后该位进位 0;
      • ai = bi = 1,则计算后该位进位 1。
        故 ci = ai。
    • ai != bi:ai 和 bi 一个为 0,一个为 1,相加后均不会进位,考虑到 ci = 0,因此 ci 不做处理,而 ans 该位置为 1。
  2. ci = 1
    • ai = bi:ai 不是 0 就是 1,因此相加后该位结果均为 1,将 ans 该位置为 1。
      • ai = bi = 0,则计算后该位进位 0;
      • ai = bi = 1,则计算后该位进位 1。
        故 ci = ai。
    • ai != bi:ai 和 bi 一个为 0,一个为 1,因此相加后该位结果均为 0,并且产生进位。因此 ans 不做处理,ci 变为 1。考虑到该分支的前提是 ci 已经为 1,因此该情况跳过即可。
public class Solution {
    public int Add(int a, int b) {
        int ai, bi, ci = 0, i = 1, ans = 0;
        do {
            ai = (a & i) == 0 ? 0 : 1; // 获取 a 的每一位
            bi = (b & i) == 0 ? 0 : 1; // 获取 b 的每一位
            if (ci == 0) {             // 进位为 0
                if (ai == bi) ci = ai;
                else ans |= i;
            }
            else if (ai == bi) { // 进位为 1
                ci = ai;
                ans |= i;
            }
            i <<= 1; // 左移 i
        } while (i != 0);
        return ans;
    }
}
  • 时间:20 ms,击败 77.78% 使用 C# 的用户
  • 内存:25.95 MB,击败 94.44% 使用 C# 的用户

文章来源:https://blog.csdn.net/zheliku/article/details/134838228
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。