两个按位运算的等价性

Question

以下两个C函数是等效的:

unsigned f(unsigned A, unsigned B) {
  return (A | B) & -(A | B);
}
unsigned g(unsigned A, unsigned B) {
  unsigned C = (A - 1) & (B - 1);
  return (C + 1) & ~C;
}

我的问题是:为什么它们相同？将g它转化为什么规则/变换f？

Answer 1

1a.表达式x & -x是一个众所周知的"位黑客":它计算的值0除了一位之外所有位都设置为:1原始值中的最低位x.(当然,除非x是0.)

例如,在无符号算术:5 & -5 = 1,4 & -4 = 4等

2a.这立即告诉我们什么功能f呢:通过使用|运营商整合了所有1位A和B,然后找到最低1的总价值.换句话说,结果f是,包含一个唯一字1中的最低的位置位1在A或B.

1b.表达式(x + 1) & ~x是一个众所周知的"位黑客":它评估所有设置为0除0原始值中最低位的位x.最低0位x成为1结果值中的唯一值.(x当然,除非是全1位.)

例如,在无符号算术:(5 + 1) & -5 = 2,(4 + 1) & -4 = 1等

2b.表达式x - 1替换所有尾随0在位x与1和替代最低的1在x用0,保持其余x不变.运算符&组合所有0位(就像运算符|组合所有1位).这意味着(A - 1) & (B - 1)它将具有最低0位所在的最低1位A或B.

3b.每1b,用一个单独(C + 1) & ~C替换最低,将其他所有内容归零.01

这意味着g做同样的事情f.两个函数都查找并返回1两个输入值之间的最低位.结果总是2的幂(或只是0).例如,如果至少一个输入值是奇数,则结果为1.

我有一种直觉(可能是错误的),为了通过对现有表达式应用附加操作来构建一个函数到另一个函数的正式转换,需要这些函数中的至少一个是"可逆的"(是一些半非正式的含义).这两个看起来都不够"可逆"给我......