Równanie na bitach

Mam za zadanie napisać program który rozwiąże równanie x + y = x | y (gdzie znak '|' to bitowy or). Odpowiedzią do zadania jest k-te najmniejsze rozwiązanie tego rownania dla ustalonego x'a (rozwiązania liczymy od zerowego). Na wejściu mamy dwie liczby (1 <= x,k <= 10^9) Np. dla x = 5 i k = 1 odpowiedzią jest 2, a dla x = 10 i k = 3 odpowiedzią jest 5. Napisałem poniższy program, ale czas obliczania przekracza limit, który wynosi 1s. Prosiłbym o jakąś pomoc/wskazówkę jak przyspieszyć ten program.

Wymyśl lepszy algorytm. To jest: nie siłowy. Takie zadania są na myślenie, nie na sprawdzenie wszystkich możliwych liczb.

Podpowiedź: procesor jakoś dodaje do siebie liczby. Jak?

Tak właśnie myślałem, ze musi być na to jakiś sprytny sposób. Co do działania procesora to mało wiem, ale spróbuje poszukać jakichś informacji w internecie.

Niestety dalej, nie widzę żadnej zależności między or'em a binarnym dodawaniem. Wszystko co wymyślę sprowadza się do sprawdzania binarnej postaci kazdej liczby po kolei.

Alternatywnie możesz sobie dodać dwie liczby binarne na kartce. Bez używania dodawania. Też powinieneś zobaczyć co trzeba, jeśli będziesz patrzeć.

Chyba już mam. Spróboje wymyślić jeszcze jak przełozyć to na algorytm i dam znać.

Doszedłem do tego, ze rozwiązaniami takiego równania są wszystkie możliwe kombinacje zmian zer na jedynki, tzn. (gdy 10 to 1010 to rozwiązaniami będą 0101, 0001, 0100 oraz poprzednie liczby zwiekszone o 16). Próbowałem to zaimplementować, ale nic ciekawego z tego nie wyszło. Najpierw zamieniam liczbę na system binarny, a potem chciałbym szukać tych rozwiązań, ale nie mam pomysłu jak sie do tego zabrać.

Interesuje cię tylko k-te rozwiązanie. Koniunkcja i i x musi być zerowa, do tego już doszedłeś. k-ta kombinacja zmienionych zer na jedynki to liczba k, której bity zostały zapisane w polach, gdzie w x są zera. Do zaimplementowania tego nie potrzeba żadnych konwersji.