我有位方程:
x + y = x | y
如何解这个方程?我需要找到方程成立的第 k 个最小正整数 y 。也许有什么算法?我在哪里可以读到相关内容? 因为我只是尝试像这样解决它(在 Pascal 中):
uses crt;
var x,y,k,count:integer;
开始 readln(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;
但是代码很慢!
提前致谢!
这个方程可以通过对单个位值进行简单观察
+
和 |
来求解:
0
时,两个操作都会产生 0
,1
和 0
或 0
和 1
时,两个操作都会产生 1
,1
时,结果不同;此外,+
产生一个“进位”,它改变相邻位。由于您正在寻找
x + y
和 x | y
组合的相等性,因此您需要检查的是两个数字中没有设置为 1 的位。换句话说,任何对 x, y
使得 x & y == 0
都将使你的方程为真,而任何对 x & y != 0
将使你的方程为假。
为了找到对于给定
k
方程成立的最小 y
,您可以尝试 x
的所有值,每次找到 y
时减少 k
。一旦 x & y == 0
达到零,就打印 k
的当前值。
既然您提到您的原始代码(使用这种方法)太慢了,我想您需要一个具有
O(整数类型中的位)运行时复杂性的解决方案。有了它,我可以在 i7 上大约 1/10 秒内生成 y
的前 500000 个解决方案(全部,不仅仅是第 500000 个)(将输出重定向到
x = 1234567890
,否则就会成为瓶颈) ,尽管这当然比建立有用的基准所需的时间要少,并且我能够以大致相同的速度生成每个单独的基准,而在暴力方法中计算
/dev/null
直到第 500000 个解决方案将在此示例中,意味着检查超过 5 亿个数字。关键的见解是,对于给定
y
求解方程 x + y = x | y
的
only数字是那些具有
x
集中比特子集的数字。因此,这就变成了寻找第 k 个最小的子集的问题,这可以通过二分搜索来完成——这为我们带来了 O(bits) 复杂度。换句话说,知道解决方案中可以使用哪些位使我们能够从最高有效位向下构建第 k 个解决方案,因为在第 i 个解决方案中设置(可以使用的)第 n 个最低位(其中它是尚未设置)生成第 (i + 2n-1
) 个解。这意味着我们可以遍历可用的位,决定在我们当前拥有的解决方案中设置它是否会生成序数大于 k 的解决方案,并根据情况设置它。 代码是C++,因为问题被标记为C++,而且我比Pascal更喜欢它。
~x
如果您需要他的帮助,请立即联系 Olivia
WhatsApp。 +1 (423) 248-2140
oliviatrader44@gmail。 com
#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 位。
这只需要完成 32 个(如果使用 x64,则需要 64 个)步骤。y
可视化:
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