Решения уравнений бит

Question

У меня есть битовое уравнение:

x + y = x | y 

Как решить это уравнение? Мне нужно найти k-ое наименьшее положительное целое число y, для которого выполняется уравнение. Может быть, есть какой-то алгоритм? Где я могу прочитать об этом? Ofcause я просто пытался решить, как это (в Pascal):

uses crt; 
var x,y,k,count:integer; 

начинает ReadLn (х, к); 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; 

Но код очень медленный!

Заранее благодарен!

Answer 1

Это уравнение может быть решена путем простого наблюдения о + и | на одном битовое значение:

• Когда оба значения 0, обе операции производят 0,
• Когда значения 1 и 0 или 0 и 1, обе операции производят 1,
• Когда оба значения равны 1, lts разные; также, + производит «перенос», который изменяет смежный бит.

Поскольку вы ищете равенство x + y и x | y комбинаций, все, что вам необходимо проверить, что нет бит, установленных в 1 в обеих номерах. Другими словами, любая пара x, y такая, что x & y == 0 сделает ваше уравнение истинным, а любая пара, такая что x & y != 0 превратит ваше уравнение в ложное.

Для того, чтобы найти k наименьшее y, для которых уравнение имеет место для данного x, вы можете попробовать все значения y, декремента k каждый раз, когда вы найдете x & y == 0. Как только k достигнет нуля, напечатайте текущее значение y.

Answer 2

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

Answer 3

Простейшее ответ на это отрицание:

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; 

Answer 4

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

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

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

Другими словами, зная, какие биты могут использоваться в решении, мы можем построить k-е решение из наиболее значимого бита вниз, поскольку установить бит nth-lower (из тех, которые могут быть использованы) в i-м решении (в котором он еще не установлен) генерирует решение (i + 2 ^n-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"; 
    } 
}