python 解决lintcode a+b 超时问题

题目描述

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
            
        }
阅读 935
评论
    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

    评论 赞赏
      撰写回答

      登录后参与交流、获取后续更新提醒