使用按位运算最多三个整数？

如何仅使用按位操作返回最多三个无符号整数，例如！，〜，|，＆，^，+，>>，<<。 我不知道从哪里开始。 任何帮助，将不胜感激。

编辑：

我只被允许使用给定的合法操作，就是这样。

/** maxOfThree - Returns the maximum of three integers. * NOTE: x, y, z are all in the range [0, TMax]. * Examples: maxOfThree(1, 2, 3) = 3 * Legal Ops: ! ~ & ^ | + <> * Max Ops: 25 int maxOfThree(int x, int y, int z) { } 

Answer 1

看看“ bit-twiddling hacks ”页面，研究如何实现最大/最小化。

如果你可以弄清楚两个数字的最大值是如何工作的，那么你可以概括三个数字的情况。

让我向您解释获得最大值的两个数字的情况：

---

-(a可以返回-1或0，然后你可以有11111111 11111111 11111111 11111111 （对于int的二进制补码为-1）或者00000000 00000000 00000000 00000000 （对于int为-0 == 0）。

记住a^b^b = a和a^b^a = b （无论顺序是什么，这是xor操作），你在第一种情况下有：

• 如果a < b你需要返回b作为结果，那么

a ^ ((a ^ b) & -(a < b))必须等于a ^ a ^ b ..事实上它是-(a返回11111111 11111111 11111111 11111111 ，并且按位和按位＆ 11111111 11111111 11111111 11111111对无符号整数运算使数字保持不变...因此a ^ a ^ b = b 。 这是最大的。

• 如果a > b则a < b为假，因此(anything & 00000000 00000000 00000000 00000000)为0.因此你有a ^ 0 ，即a。 最大值。

最后我们将解决方案推广到三个数字：

 #include  int getMax(unsigned int a, unsigned int b, unsigned int c) { int temp = a ^ ((a ^ b) & -(a < b)) ; int r = c ^ ((c ^ temp) & -(c < temp)); return r; } int main(void) { unsigned int a = 3, b = 1, c = 9; printf("%d", getMax(a,b,c)); return 0; } 

---

编辑：如果您不允许使用“<”，则使用第二个版本

 x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); 

并记住以下摘录

请注意，1989 ANSI C规范未指定签名右移的结果，因此这些不可移植。 如果在溢出时抛出exception，那么x和y的值应该是无符号的或转换为无符号的减法以避免不必要地抛出exception，但是右移需要带符号的操作数在负数时产生所有的一位，所以强制转换在那里签名

---

编辑II：这应该适用于您发布的规范：

 #include  int getMax(int x, int y, int z) { int r = (x + ~((x+~y+1) & ((x+~y+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31 int r2 = (z + ~((z+~r+1) & ((z+~r+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31 return r2; } int main(void) { unsigned int a = 5, b = 7, c = 1; printf("%d", getMax(a,b,c)); return 0; } 

请注意，如果您可以使用sizeof（）而不是假设int是4个字节（在所有平台上都不是这样）会更好。

Answer 2

如果你被允许使用- （你建议+ ），我建议以下（未经测试），我认为比比特翻页更有效，特别是如果第一个最大值是宏，我们知道我们正在处理签名整数。

 #define MAX2(a,b) (a-((ab) >> (sizeof(int) * CHAR_BIT - 1))*(ba)) int max3 (int x, int y, int z) { return MAX2(MAX2(x, y), z); } 

在大多数平台上， CHAR_BIT应该是# #define到8。

这也依赖于负数右移的未定义行为。

如果您不被允许使用- ，请使用~并添加1。

David Kernin的答案更为笼统。