Search code examples
c++algorithmpascalbit

Solving bits equations

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!

Solution

  • This equation can be solved by making a simple observation about + and | on a single bit value:

    • When both values are 0, both operations produce 0,
    • When the values are 1 and 0 or 0 and 1, both operations produce 1,
    • When both values are 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.