求解位方程

Question

我有位方程：

x + y = x | y

这个方程怎么解？我需要找到等式成立的第 k 个最小正整数 y。也许有任何算法？我在哪里可以读到它？ Ofcause 我只是想像这样解决它（在 Pascal 中）：

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

开始读取（x，k）；计数：=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

解的总数是x和y值可能组合总数的3/4。这是因为只要 x + y 中没有进位，您的方程式就会得到满足。所以对于每一位，对应x和y位00、01和10的三种组合不产生进位，只有11产生进位。

Answer 2

这个等式可以通过对单个位值的 + 和 | 进行简单观察来求解：

当两个值都是0时，两个操作都会产生0，
当值为1和0或0和1时，两个操作都会产生1、
当两个值为1时，结果不同；此外，+ 会产生一个 "carry"，它会更改相邻位。

由于您正在寻找 x + y 和 x | y 组合的相等性，您需要检查的是两个数字中没有设置为 1 的位。换句话说，任何一对 x, y 使得 x & y == 0 将使你的方程为真，而任何一对 x & y != 0 将使你的方程为假。

为了找到 k 最小的 y 方程适用于给定的 x，您可以尝试 y 的所有值，递减 k 每次找到 x & y == 0。一旦 k 达到零，打印 y.

的当前值

Answer 3

最简单的答案就是否定：

unsigned y = ~x;

因为(x & ~x) == 0.

要获得 k-th，您应该将 k 的位映射到 y 的 1 位。这将仅完成 32 个（如果您使用 x64，则为 64 个）步骤。

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（整数类型的位）运行时复杂度的解决方案。有了它，我可以在我的 i7 上大约 1/10 秒内为 x = 1234567890 生成前 500000 个解决方案（所有这些，而不仅仅是第 500000 个）（将输出重定向到 /dev/null，否则成为瓶颈），尽管这当然比一个有用的基准测试所需的时间要少，并且我能够以大致相同的速度生成每个单独的基准测试，而计数 y 在这个例子中，暴力方法中的第 500000 个解决方案意味着要检查超过 5 亿个数字。

要获得的关键见解是，仅解给定 x 方程 x + y = x | y 的数字是那些具有~x 中的位设置。因此，这就变成了寻找第 k 个最小这样的子集的问题，这可以通过二进制搜索来完成——这为我们带来了 O(bits) 复杂度。

换句话说，知道哪些位可以在一个解决方案中使用使我们能够从最高有效位向下构造第 k 个解决方案，因为在第 i 个解决方案中设置第 n 个最低位（可以使用的那些）（其中尚未设置）生成第 (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";
  }
}

求解位方程

Solving bits equations

c++

algorithm

pascal

bit