Python solves the problem of lintcode astatb timeout

topic description

lintcode aquib problem

sources of topics and their own ideas

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

Code

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

Why does the code time out when await murb? by the same logic, there is no timeout with 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
            
        }
Jun.23,2022

< H2 > original code, inverse code and complement < / H2 >

We plastic data take octet as an example
then use the integer 5 to give an example:

  • original code: 0000 0101
  • reverse code: 1111 1010
  • complement: 1111 1011

and complement is negative in the computer binary representation

< H2 > shift operation < / H2 >

< and > simply move the specified number of digits to the left or right, the vacancy is filled with 0 or 1, and the overflow will be discarded

< H2 > back to the question < / H2 >

1. Calculate a ^ b (take + 5,-5 as examples )

and a and -a perform XOR operations
to get 1111 1110
, that is, -2

calculation process:
take 5 (0000 0101) and -5 (1111 1011) as examples
XOR operation to get 1111 1110
1111 1110 minus 1 to get 1111
11111101 take the reverse code 00000010 to get 2
and then add the original minus sign that is -2

2. Calculate (aqb) < < 1 (take + 5,-5 as an example )

and a and b perform and operations
to get 0000 0001
and then move one bit to the left
to get 0000 0010
that is, 2

calculation process:
also take 5 (0000 0101) and -5 (1111 1011) as examples
and after
get 0000 0001
and then move one bit to the left
to get 0000 0010
, that is, 2

3.So

as you can see, "any" one set of opposite numbers , running a cycle will get another set of opposite numbers
So, this group of opposite numbers run again, get another set of opposite numbers .

So if the loop goes on indefinitely, of course it will time out.
you can add in your code that if the absolute values of an and b are equal , then they are directly equal to 0
. Actually, there is a certain pattern. I don't want to explore
clipboard.png

print(a, b),
clipboard.png

.
Menu