采取共同进行按位或操作

Question

的。如果我们有一个操作（X A | X乙），其中“|“是” OR“操作，然后你会被要求采取X为止的动作，并得到由左的结果相乘。

例如，让P =（X A | X B）

后来不知怎的，P = X *（这里的一些表达）

请让我知道这是可能的这将是什么表达。

Answer 1

对于这个答案，我会认为32位整数（这是更普遍的实际，但它并不适用于ℤ工作）。

这是可能的，但是这不是最优化。考虑x是奇数的情况：

x有一个模乘法逆，我们称之为inv(x)。现在插入模板
P = x * Expr，Expr = inv(x) * (x * A | x * B)

所得的表达是x * inv(x) * (x * A | x * B) = x * A | x * B。

考虑到x甚至情况。观察乘以2 x使得x * A | x * B两倍大太，即使非线性“或”操作涉及，因为乘以2就是一个左移和左移分布在OR。

因子x成其中y是奇数和d是二的幂。现在让“均匀”来自最后的乘法x，并写出Expr = inv(y) * (y * A | y * B)。

将其插回到模板中，我们得到y * d * inv(y) * (y * A | y * B)，它简化为d * (y * A | y * B)，这又是x * A | x * B。

这种情况实际上是一般情况，因为对于奇数x，d可以设置为等于1。