python 解决lintcode a+b 超时问题

zslqy
  • 9

题目描述

lintcode a+b 问题

题目来源及自己的思路

https://www.lintcode.com/prob...

代码

def aplusb(self, a, b):
    # write your code here
    while True:
        a, b = a^b, (a&b)<<1
        if a==0 or b == 0:
            return a or b

当 a=-b 时 为什么代码会超时, 而同样的逻辑,用Java就不会超时

  public int aplusb(int a ,int b) {
        // write your code here, try to do it without arithmetic operators.
        while(true){
        int x = a^b;  //记录不进位数
        int y = (a&b)<<1;  //记录进位数
        if(x==0){
            return y;
        }
        if (y==0){
            return x;
        }
        a=x;
        b=y;
        } // while
            
        }
回复
阅读 1.8k
1 个回答

原码、反码和补码

整形数据八位二进制为例
那用整数5举个例子吧:

  • 原码: 0000 0101
  • 反码: 1111 1010
  • 补码: 1111 1011

补码就是负数在计算机中的二进制表示方法

移位操作

<<>>简单的说就是向左或向右移动指定的位数, 空缺用0或1来补, 溢出的部分将被舍弃

回到题中

1.计算a^b(以+5、-5为例)

a-a进行异或操作
得到1111 1110
也就是-2

计算过程:
5(0000 0101)-5(1111 1011)为例
异或运算得到1111 1110
1111 1110 减去 1 得到 1111 1101
1111 1101 取反码 0000 0010 得到 2
2再加上原来的负号 就是 -2

2.计算(a&b)<<1(以+5、-5为例)

ab进行"与"操作
得到0000 0001
左移一位
得到0000 0010
也就是2

计算过程:
同样以5(0000 0101)-5(1111 1011)为例
"与"
得到0000 0001
左移一位
得到0000 0010
也就是2

3.So

你可以看到, "任意"一组相反数, 运行一次循环都会得到另一组相反数
So, 这一组相反数再运行一次, 得到另一组相反数......

So无限循环下去当然会超时了
你可以在代码中加上如果a, b的绝对值相等, 则直接等于0
其实还是有一定规律的, 我不想探究了(捂脸)
clipboard.png

加上print(a, b), 自己看吧
clipboard.png

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏