c++ - 我无法理解方程式的解，该方程式表示找到最小数，使得 x 加 y 等于 x 按位或 y

Question

问题是找到满足以下等式的第k小数(y)x + y = x |是的。

例如:x = 5 kthSmallest = 1 给出 y = 2 为 5+2 = 5 | 2

我使用基本方法对其进行编码

long kthPlusOrSolutionMine(int x, int k){
int kthSolution = 1;
for(int i=0;i>=0 ; i++ ){
    int rhs = x | i;
    int lhs = x + i;
    if(rhs == lhs){
        kthSolution++;
        if(kthSolution == k)
            return i;
    }
    return 0;
}
}

然而，我找到了同样问题的另一种解决方案，但我无法完全理解它。

long kthPlusOrSolution(int _x, int k) {
long x = _x;
long y=0,t;
for(t=1; k; t=t<<1, k=k>>1){
    //cout << "t is " << t << " x is " << x << " k is " << k <<endl;
    //cout << (t&x) << endl;
    while(t&x)
        t=t<<1;
    if(k&1)
        y = y|t;
}
return y;
}

有人可以帮助我理解它是如何工作的吗？

Answer 1

按位，可以比较加法与或的真值表(C为加法进位):

A B + C | A+B==A|B
0 0 0 0 0   yep
1 0 1 0 1   yep
0 1 1 0 1   yep
1 1 0 1 1   nope

所以你可以这么说

• 对于X的每一位设置为1，Y的相应位必须为零。
• 对于X的每一位设置为0，Y的对应位可以是0或1。

让我们对 y 中允许从 0 到 I 变化的位进行编号。

x 0 0 1 0 0 1 1
i 3 2 - 1 0 - -

请注意，如果我们将 Y_i 称为第 i_th 位设置为 1 的数字，则 Y_i 是解决方案编号 2< sup>i+1 的等式。

例如:

x  = 010011
y    0-00--
y1 = 0-01-- 2nd
y2 = 0-10-- 3rd
     0-11-- 
y3 = 1-00-- 5th
     1-01--
     1-10--
     1-11-- 
y4 =10-00-- 9th

另请注意，第 i_th 位设置为 0 和同一位设置为 1 的解之间的秩差为 2ⁱ。

例子:秩为2的位是变化的

0-00-- 1st
1-00-- 5th

排名差异:2² = 4

这意味着设置y 的i_th 位|到 1 跳过 2ⁱ 个解决方案。
这是为算法提供动力的神奇属性。

在每个循环中，t设置为 x 的第 i 位(例如，如果 x = 11，t 的连续值将是 4、8、16 等)

k分解为 2 的幂。在每个循环中，检查基数 2 中 k 的第 n_th 位，并且每次 y更新后，使用我们的魔法属性消除了 2ⁿ 个解决方案。

例子:如果 k = 5 (1001b)

1st loop k = 5 -> eliminate 2^0 = 1 solution
2nd loop k = 2 -> does nothing
3rd look k = 1 -> eliminate 2^2 = 4 solutions

在导出处，y设置为第5解。
或者更准确地说，第 5 个解不同于 0，
如果您将零算作(平凡的)解决方案，则这是第 6 个。