leetcode Sum of Two Integers

leetcode Sum of Two Integers

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.

传送门:leetcode Sum of Two Integers

题意:给定两个数 a和b,求它们的和。 要求不使用 +和-运算符

思路:

首先要知道,异或也被称为“模2和” ,so 这题就是运用异或的位运算啦。

我们可以每次取最低位来计算, 然后每次右移一位,注意点有:

  • 进位为两个数字1
  • 负数的情况下,右移最高位补的是1 ,因此值得注意要取到什么时候为止。 java有一个无符号右移>>>高位补0,因此结束条件可以为a!=0 || b!=0(然而进位会被忽略)

C++

Java

 

第二种方法是直接进行异或操作。

a ^ b 直接算出a + b 每位上%2的结果, 进位的话可以直接 (a & b)<<1得到(只有两个位均为1才会进位嘛,左移表示进到下一位啊)

C++

Java(和上面一样)

也可以写成Oneline:

 

PS:

Python 表示一个数不止32位。。

Of course, Python doesn’t use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written “…1111111111111111111011”.
来自 https://wiki.python.org/moin/BitwiseOperators

因此。。做这题要保证两个数在正确的范围内(本题是int,32bit)

如何做到呢?我们知道32bit 可以表示的无符号整数位0~0xFFFFFFFF(全0~全1)

因此,我们使用&来保证该数是32bit.

int的0和正整数范围为0~0x7FFFFFFF,int负数的范围为-0x80000000~-1,因此,大于0x7FFFFFFF的其实是最高位为1(这是符号位)。这样算出来是把最高位不当成符号位,我们还需要对负数的情况进行修正。

在具体实现上,我们可以先 &0x7FFFFFFF 然后取反,这样,-1变为-0x80000000(-2147483648) -2变为了-0x7FFFFFFF(-2147483647) ,因此,在^0x7FFFFFFF即可。。

也可以看https://discuss.leetcode.com/topic/49900/python-solution/2 上的思路

或者更巧妙的用(~0 << 31) | a 即可,因为只需要把31位之后的全部置1, 感谢mach7提出

 

 

 

本题是leetcode 371 Sum of Two Integers 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Sum of Two Integers
本文地址:https://www.hrwhisper.me/leetcode-sum-two-integers/

听说帅的人已经打赏了

Leetcode , , , . permalink.

9 thoughts on “leetcode Sum of Two Integers

  1. Java的方法中 carry 如果是 0010那肯定没问题。 但是如果carry是 0110怎么办?这方法也同样适用吗? (应该是可以的)

  2. 我觉得你的第一种解法的java版本有问题。。因为循环的跳出条件如果不是32次的话,可能会有进位,这个进位是没有加上去的。

  3. 您好,能不能解释的再具体一点儿,关于对负数情况的修正。我来说的具体一些吧,假设不对负数修正,如果结果是-64,得出的是4294967232,如果表示为二进制,可以看出来是-64的掩码表示。之后我按最后修正负数的语句“~(a & MAX_INT) ^ MAX_INT”, 走了一遍,如果是二进制表示,其实就是没有表变化,为什么十进制就由4294967232变为了-64呢,琢磨了很久,没搞明白。

    • C++ /java int类型有32位,最高位就是符号位。
      比如-64应该表示为0XFFFF FFC0 前面都是1

      而python的整形不知道有多少位。这里假设它int的位数有64位呢 ?
      0X0000 0000 FFFF FFC0 算出来没修正是这个
      0X0000 0000 7FFF FFC0 &int_max
      0XFFFF FFFF 8000 003F 取反
      0XFFFF FFFF 7FFF FFC0 ^ int_max
      就是把前面的0也变成1了,让python认为是个负数- –

Leave a Reply

Your email address will not be published. Required fields are marked *