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
}
< 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
print(a, b),
.
