I'm aware that there is an accepted solution, but there is a much faster way to find the kth-smallest integer for which this solution holds than brute-forcing a solution the way it recommends.
Since you mentioned that your original code (which uses this approach) is much too slow, I figured you'd like a solution that has O(bits in the integer type) runtime complexity. With it, I can generate the first 500000 solutions (all of them, not just the 500000th) for x = 1234567890 in about 1/10th of a second on my i7 (redirecting the output to /dev/null, otherwise that becomes the bottleneck), although that is of course less time than would make for a useful benchmark, and am be able to generate each individual one with roughly the same speed, whereas counting y up to the 500000th solution in the brute-force approach would mean, in this example, checking over 500 million numbers.
The key insight to have is that the only numbers that solve the equation x + y = x | y for a given x are those that have a subset of the bits in ~x set. Thus this becomes a question of finding the kth-smallest such subset, and that can be done with a binary search -- this nets us the O(bits) complexity.
In other words, knowing which bits can be used in a solution enables us to construct the kth solution from the most significant bit downwards because setting the nth-lowest bit (of those that can be used) in the ith solution (in which it is not yet set) generates the (i + 2n-1)th solution. This means we can walk through the usable bits, decide for each whether setting it in the solution we currently have would generate a solution with an ordinal number greater than k, and set it or not depending on that.
The code is C++, because the question is tagged C++ and I like it better than Pascal.
#include <bitset>
#include <iostream>
#include <stdexcept>
// An artifact of the development process. I used it to test that
// the exception is thrown properly if there are less than k solutions.
enum { BITS_USED = 31 };
// Counts the bits set in an integer
unsigned bitcount(unsigned x) {
unsigned count = 0;
while(x != 0) {
++count;
x &= x - 1;
}
return count;
}
// Finds the highest bit set in x, starting to look at start
// (which will be the previously highest bit the way we use it)
unsigned highest_set_bit(unsigned x, unsigned start = 1 << (BITS_USED - 1)) {
unsigned mask = start;
while(mask != 0 && (x & mask) == 0) {
mask >>= 1;
}
return mask;
}
// This function does the binary search.
unsigned find_kth_complement(unsigned x, unsigned k) {
// (rest_mask) is the complement of (x), or at least the bits we take into
// consideration (see comment on BITS_USED above).
unsigned rest_mask = ~x & ((1u << BITS_USED) - 1);
unsigned rest_bits = bitcount(rest_mask);
unsigned bit = highest_set_bit(rest_mask);
// (curmask) will be updated to contain the bits we already know the
// (k)th solution will have set. It will be built from the most significant
// bit downwards and always be a solution itself (!). Setting new, ever
// less significant bits in it will make it larger until it is the (k)th
// solution.
unsigned curmask = 0;
while(rest_mask != 0) {
rest_mask &= ~bit;
--rest_bits;
// Here now the binary search: We know that (rest_bits) bits are
// set in (rest_mask), which is (~x) without the bits we already
// know the solution will have set. We know therefore that there
// are (skip) = 2^(rest_bits) solutions that have the bit in (bit)
// set, and equally many that have it unset.
unsigned skip = 1u << rest_bits;
// So: Setting the highest bit of the rest mask in (curmask) will
// propel (curmask) (skip) solutions ahead. We can only do this if
// we still have to skip more than that many solutions. (k) will
// be adjusted to be the number of solutions left to skip.
if(k >= skip) {
curmask |= bit;
k -= skip;
}
bit = highest_set_bit(rest_mask, bit);
}
// if (k) is not zero here, there were not enough solutions to skip.
if(k != 0) {
throw std::logic_error("There are less than k solutions for the given x");
}
return curmask;
}
int main() {
unsigned x = 1234567890;
unsigned y = ~x & 0xff;
std::cout << std::bitset<BITS_USED>(x) << std::endl;
// Taking it for a ride here: Generate the first 500k solutions.
// Printing them is done in binary because it is easier to see that it
// works that way.
for(unsigned i = 0; i < 500000; ++i) {
std::cout << std::bitset<BITS_USED>(find_kth_complement(x, i)) << "\n";
}
}
x + yis equal tox | ywhen~(~x | ~y)is zero - Columbox & yis 0. One way to prove that would be to prove thatx+y === (x|y)+(x&y)- rici