0

假设我正在寻找具有某些值的按位函数，例如 -

f(0b00,0b00)!=0         
f(0b00,0b10)==0     
f(0b10,0b10)!=0     
f(0b11,0b10)!=0     
f(0b01,0b10)==0

是否有为此类系统构造单个按位表达式 f 的通用方法？（我不确定，但认为如果你有巨大的表达式一次屏蔽一个位，可能会有糟糕的解决方案，所以假设表达式必须适用于所有大小的整数）

我能做的最好的转换是

f(int a, int b) 
{
    if (a==0    ) {
        return b==0;
    } else {
        return (a&b)!=0;
    }
}

我怀疑很难将 (x==0) 条件与 (x!=0) 条件结合起来（给定 x，是否有一个按位函数 f 使得 x==0 <=> f(x)!=0 ? )，但我不知道这里有多少障碍。

任何答案都会引起极大的兴趣:)

和平，

小号

4

1 回答 1

1

最通用的结构是“minterms”的扩展版本。如果输入与特定事物匹配，则使用按位运算符构造一个为 -1 的谓词，并将谓词与您想要的结果相匹配，然后将所有这些事物组合在一起。这当然会导致可怕的表达，可能是指数级的。

使用算术右移，您可以构造一个谓词p(x, c) = x == c：

p(x, c) = ~(((x ^ c) >> 31) | (-(x ^ c) >> 31))

将 31 替换为 int 减一的大小。

它和它的否定都是非负的唯一数字是零。所以最后补码里面的东西只有零 if x ^ c == 0，和那个说的是一样的x == c。

因此，在此示例中，您将拥有：

(p(a, 0x00) & p(b, 0x00)) |
(p(a, 0x10) & p(b, 0x10)) |
(p(a, 0x11) & p(b, 0x10))

把它扩展成可怕的东西。

显然，这种结构通常不会给你任何明智的东西。但是很一般。

在具体示例中，您可以执行以下操作：

f(a, b) = (p(a, 0) & p(b, 0)) | ~p(a & b, 0)

可以再次简化一点（显然，如果 ，则异或消失c == 0，并且两个补码相互平衡）。

于 2013-09-18T11:05:47.160 回答