解bits方程
解bits方程
提问于 2015-02-01 23:08:32
我有位方程：
x + y = x | y如何解这个方程？我需要找到方程成立的k个最小正整数y。也许有什么算法？我在哪里能读到它？因为我只是试图像这样解决这个问题(在Pascal中)：
uses crt;
var x,y,k,count:integer;开始读(x，k)；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;但是代码太慢了！
提前感谢！
回答 3
Stack Overflow用户
回答已采纳
发布于 2015-02-01 23:19:36
通过简单观察单比特值上的+和|，可以解决这个方程：
- 当两个值都是
0时，两个操作都生成0， - 当值为
1和0或0和1时，这两个操作都生成1， - 当两个值都是
1时，结果是不同的；而且，+会产生一个“进位”，这会改变相邻的位。
由于您正在寻找x + y和x | y组合的相等性，所以只需检查两个数字中没有设置为1的位。换句话说，任何一对x, y，如x & y == 0将使您的方程成立，而任何一对x & y != 0都将使您的方程变为假。
为了找到方程对于给定的k的最小y，您可以尝试y的所有值，每次找到x & y == 0时都会递减k。一旦k达到零，就打印y的当前值。
Stack Overflow用户
发布于 2015-02-01 23:17:29
解的总数是x和y值可能组合总数的3/4。这是因为当x+ y中没有进位时，你的方程就会满足。因此，对于每一个位，对应的x位和y位的三个组合-- 00，01和10 --生成无进位，只有11生成进位。
Stack Overflow用户
发布于 2015-02-01 23:24:08
最简单的答案是否定：
unsigned y = ~x;因为(x & ~x) == 0。
要获得k-th，您应该将k位映射到1位y。这将只完成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;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28269037
复制相关文章
相似问题
腾讯云开发者
