当前位置:   article > 正文

371.两个整数之和-力扣leetcode_力扣两整数之和

力扣两整数之和

题目 : 给你两个整数 a 和 b ,不使用 运算符 + 和 - ,计算并返回两整数之和。

   当时看到两个数和我惊了,还有这题??后来仔细发现不能用运算符,那么就有意思了

这题需要用到位运算的知识:
预备知识

有符号整数通常用补码来表示和存储,补码具有如下特征:

正整数的补码与原码相同;负整数的补码为其原码除符号位外的所有位取反后加 11。

可以将减法运算转化为补码的加法运算来实现。

符号位与数值位可以一起参与运算。

思路和算法

虽然题目只要求了不能使用运算符+ 和 -,但是原则上来说也不宜使用类似的运算符 \texttt{+=}+= 和-= 以及sum 等方法。于是,我们使用位运算来处理这个问题。

首先,考虑两个二进制位相加的四种情况如下:


0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (进位)
可以发现,对于整数 aa 和 bb:

在不考虑进位的情况下,其无进位加法结果为 a⊕b。

而所有需要进位的位为 a & b,进位后的进位结果为(a & b) << 1。

于是,我们可以将整数 aa 和 bb 的和,拆分为 aa 和 bb 的无进位加法结果与进位结果的和。因为每一次拆分都可以让需要进位的最低位至少左移一位,又因为 aa 和 bb 可以取到负数,所以我们最多需要 log(max_int) 次拆分即可完成运算。

因为有符号整数用补码来表示,所以以上算法也可以推广到 00 和负数。

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/811593
推荐阅读
相关标签
  

闽ICP备14008679号