仅具有按位运算的两个简单表达式的相等性

Question

给出C语言中的以下两个函数:

int f(int x, int y, int z) {
    return (x & y) | ((~x) & z);
}

int g(int x, int y, int z) {
    return z ^ (x & (y ^ z));
}

对于任何有效整数,两个函数的结果相等.

我只是想知道两个表达式之间的数学.

我首先在维基百科的SHA-1算法中看到了函数f的表达式.

http://en.wikipedia.org/wiki/Sha1

在"SHA-1伪代码"部分中,在主循环内:

if 0 ? i ? 19 then
        f = (b and c) or ((not b) and d)
        k = 0x5A827999
...

在一些开源实现中,它使用函数g:z ^(x&(y ^ z))中的形式.

我编写了一个程序并迭代x,y,z的所有可能值,并且所有结果都相等.

如何推断表格

(x & y) | ((~x) & z) 

到形式

z ^ (x & (y ^ z))

在数学？不只是证明平等.

Answer 1

由于按位运算等效于对各个位的布尔运算,因此只需枚举{x, y, z}三元组的八个赋值即可证明等价.

填写这两个函数中的每一个的真值表,然后将八个位置相互比较.如果所有八个位置都匹配,则两个函数是等价的; 否则,功能是不同的.

你并不需要手动要么做到这一点:插上这两个功能在三个嵌套循环,给x,y和z值从零到,包容性,并比较结果调用的f(x,y,z)到g(x,y,z).