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

Question

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

编辑:

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

/** 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为二进制补码为int)或00000000 00000000 00000000 00000000(-0 == 0为int).

记住那个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)));

并记住以下摘录

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

编辑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个字节(在所有平台上都不是这样)会更好.