满足方程的按位变换算法

Question

我一直在想办法解决这个问题，有人可以给我一个算法或一组步骤的想法来解决这个问题吗？我真的很困惑。代码不是必需的。我打算用 Python3、C 和 Rust 解决它。

考虑四个数字:a、b、c 和 k。您必须最多更改 a 和 b 中的 k 位，以形成满足等式 a' | 的数字 a' 和 b' b' = c。 |表示按位或运算。

如果不存在这样的值，则返回 -1。在有多个解的情况下，使a'尽可能小；如果仍然有多个解决方案，则使 b' 尽可能小。

如果 a 中更改的位数是 k.a(类似地，b 是 k.b)，则 k.a + k.b <= k。

Answer 1

我假设所需的结果是异或掩码，即。数字中的位应更改为 1，位应保持不变的位置为 0(因此 a XOR amask = a' 和 b XOR bmask = b')

为了完整起见，a' | 的结果b' 有 1 位，其中 a' 或 b' 或两者都有 1，否则为 0。

首先，a' | 绝对必要的条件b' = c 是 a' 和 b' 都没有 1 位，而 c 有 0 位。换句话说，要获得第一个 amask 和 bmask，您可以取 a 和 b 并将每个位设置为 0，其中 c 为 1。换句话说，要获得第一个 amask 和 bmask，您可以取 a 和 b 并设置c 的二进制补码为 0 时，每一位都为 0。

amask = a & (~c)
bmask = b & (~c)  

现在计算 amask 和 bmask 中有多少位是 1(使用简单的循环，或者使用许多在线 popcount 函数之一)，然后从你的 k 中减去它。如果 k 为负数，则无解(返回 -1)。

第二部分要求你找到 a 和 b 都为 0 但 c 为 1 的位。简而言之:
temp_mask = c & ((a XOR amask) | (b XOR bmask))
temp_mask 是您需要在 a 或 b 中设置为 1 的位(哪个取决于“最小”要求。但首先，如果结果大于您剩余的，也 pop-count temp_mask k，无解(返回-1)。

下一步很简单:
amask = amask |临时掩码
之前的 amask 有 1，其中 c 为 0，现在这个语句不会重叠任何东西。

现在，对于 a' | 您至少有一个解决方案b' = c，即
(异或掩码)| (b XOR bmask) = c
但是仍然可能有另一个 a 更小的，对吧？

这也不是很难:在 (a XOR amask) 中为 1 但在 (b XOR bmask) 中为 0 的每一位都可以“移动”，即。在 (a XOR amask) 中设为 0，在 (b XOR bmask) 中设为 1。结果 c 将相同，但 (a XOR amask) 的数值将更小(可能，最坏的情况下它保持不变)。

temp_mask = (a XOR amask) & (~(b XOR bmask))  
amask = amask XOR temp_mask
bmask = bmask XOR temp_mask

要实现这一点，请注意 unsigned 和 int 大小。

完整的伪代码:

amask = a & (~c)
bmask = b & (~c) 
temp_mask = c & ((a XOR amask) | (b XOR bmask))
amask = amask | temp_mask
temp_mask = (a XOR amask) & (~(b XOR bmask))  
amask = amask XOR temp_mask
bmask = bmask XOR temp_mask