Решение битовых уравнений

Общее количество решений составляет 3/4 от общего числа возможных комбинаций значений x и y. Это потому, что ваше уравнение будет выполняться всякий раз, когда в x + y нет переносов. Таким образом, для каждого бита три комбинации соответствующих битов x и y 00, 01 и 10 не генерируют перенос, и только 11 генерирует перенос.

Я знаю, что существует приемлемое решение, но есть гораздо более быстрый способ найти k-е наименьшее целое число, для которого это решение имеет место, чем грубое решение, рекомендованное им.

Поскольку вы упомянули, что ваш исходный код (который использует этот подход) слишком медленный, я подумал, что вам нужно решение, которое имеет O (биты в целочисленном типе) сложность во время выполнения. С его помощью я могу сгенерировать первые 500000 решений (все они, а не только 500000-е) для x = 1234567890 примерно на 1/10 секунды на моем i7 (перенаправляя вывод на /dev/nullиначе это становится узким местом), хотя это, конечно, меньше времени, чем было бы для полезного ориентира, и я могу генерировать каждый с примерно одинаковой скоростью, тогда как считая y до 500 000-го решения в методе «грубой силы» в этом примере означало бы проверку более 500 миллионов чисел.

Основное понимание заключается в том, что только числа, которые решают уравнение x + y = x | y для данного x те, которые имеют подмножество битов в ~x задавать. Таким образом, это становится вопросом нахождения k-го наименьшего такого подмножества, и это можно сделать с помощью бинарного поиска — это устраняет сложность O (бит).

Другими словами, знание того, какие биты могут быть использованы в решении, позволяет нам построить k-е решение от старшего значащего бита вниз, поскольку установка n-го младшего бита (из тех, которые могут быть использованы) в i-м решении (в котором оно еще не установлено) генерирует (я + 2^н-1Решение Это означает, что мы можем пройтись по используемым битам, решить для каждого, будет ли установка этого решения в нашем текущем решении генерировать решение с порядковым номером больше k, и установить его или нет в зависимости от этого.

Код на C ++, потому что вопрос помечен C ++, и мне он нравится больше, чем на 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";
}
}

Самый простой ответ на это — отрицание:

unsigned y = ~x;

Так как (x & ~x) == 0,

Получить k-th Вы должны отобразить биты k до 1 бита y,
Это сделает только 32 (или 64, если вы используете x64) шаги для завершения.

unsigned find(unsigned y, unsigned k)
{
int i = 0, j = 0;
unsigned result = 0;
for (i = 0; i < sizeof(unsigned)*8; ++i)
{
if (y & (1 << i))
{
if (k & (1 << j))
result |= y & (1 << i);
++j;
if (k < (1 << j))
break; //we used all bits of k
}
if (y < (1 << i))
break; //we used all 1-bits of y
}
return result;
}

Визуализация:

y:     110010011
k:         11001
11  0  01 //we skip some position
r:     110000001

Чтобы получить список кулак k числа, которые вы можете сделать цикл:

for (unsigned i = 1; i <= k; ++i)
std::cout << find(~x, i) << std::endl;