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

Question

这个问题已经有答案了:

Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator? (19 个回答)

已关闭 9 年前。

如何仅使用按位运算(例如 !,~,|,&,^,+,>>,<<)返回三个无符号整数的最大值。我不知道从哪里开始。任何帮助将不胜感激。

编辑:

我只能使用给定的合法操作，仅此而已。

/** 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<b)可以返回 -1 或 0，那么你可以有 11111111 11111111 11111111 11111111 (-1 表示整数的补码)或 00000000 00000000 00000000 00000000 (-0 == 0 表示整数)。

记住a^b^b = a那a^b^a = b (无论顺序是什么，这都是 xor 操作)，在第一种情况下:

• 如果a < b你需要返回 b 作为结果，所以

a ^ ((a ^ b) & -(a < b))必须等于a ^ a ^ b ..事实上是从-(a<b)开始返回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 <stdio.h>

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)));

并记住以下摘录

Note that the 1989 ANSI C specification doesn't specify the result of signed right-shift, so these aren't portable. If exceptions are thrown on overflows, then the values of x and y should be unsigned or cast to unsigned for the subtractions to avoid unnecessarily throwing an exception, however the right-shift needs a signed operand to produce all one bits when negative, so cast to signed there

---

编辑 II:这应该符合您发布的规范:

#include <stdio.h>

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 字节(并非在所有平台上都是如此)，那就更好了。