【leetcode74】Sum of Two Integers（不用+，-求两数之和）

系统管理员 2022-04-11 06:30 242阅读 0赞

题目描述：

不用+,-求两个数的和

原文描述：

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:

Given a = 1 and b = 2, return 3.

方法一：用位运算模拟加法

思路1：

  • 异或又被称其为“模2加法“
  • 设置变量recipe模拟进位数字，模拟加法的实现过程

代码：

  1. public class Solution {
  2.     public int getSum(int a, int b) {
  3.          int r = 0, c = 0, recipe = 1;
  4.         while ((a | b | c) != 0) {
  5.             if (((a ^ b ^ c) & 1) != 0)
  6.                 r |= recipe;
  7.             recipe <<= 1;
  8.             c = (a & b | b & c | a & c) & 1;
  9.             a >>>= 1;
  10.             b >>>= 1;
  11.         }
  12.         return r;
  13.     }
  14. }

方法二：异或求值

思路二：

  • a^b,求得结果
  • a&b，求得进位
  • 相加

代码：

  1. public class Solution {
  2.     public int getSum(int a, int b) {
  3.         while (b != 0) {
  4.             int c = a & b; //carry
  5.             a ^= b; //add 
  6.             b = c << 1;
  7.         }
  8.         return a;
  9.     }
  10. }

更多的leetcode的经典算法，查看我的leetcode专栏，链接如下：

发表评论

表情：
评论列表 （有 0 条评论，242人围观）

还没有评论，来说两句吧...

相关阅读