I have the bit equation:
x + y = x | y
How to solve this equation? I need to find k-th smallest positive integer y for which equation holds. Maybe there is any algorithm? Where can i read about it? Ofcause i simply tried to solve it like this (in Pascal):
uses crt;
var x,y,k,count:integer;
begin readln(x,k); count:=0;
for y:=1 to 10000 do
if((x+y) = (x or y)) then
begin
inc(count);
if(count = k) then
begin
WriteLn('y= ',y);
break;
end;
end;
But the code is very slow!
Thanks in advance!
This equation can be solved by making a simple observation about +
and |
on a single bit value:
0
, both operations produce 0
,1
and 0
or 0
and 1
, both operations produce 1
,1
, the results are different; also, +
produces a "carry", which changes the adjacent bit.Since you are looking for equality of x + y
and x | y
combinations, all you need to check is that there are no bits that are set to 1 in both numbers. In other words, any pair x, y
such that x & y == 0
will make your equation true, while any pair such that x & y != 0
will turn your equation false.
In order to find k
smallest y
for which the equation holds for a given x
, you can try all values of y
, decrementing k
each time you find x & y == 0
. Once k
reaches zero, print the current value of y
.