c - 在c二进制文件中，测试数字是否在范围内

Question

这是我无法解开的谜题的一部分。该函数接受三个输入。第一个是 int，第二个是下界，第三个是上限。我需要测试第一个数字是否在下限和上限内(包括下限和上限)。

如果在范围内则返回1，否则返回0。问题是我只能使用

! ~ & ^ | + << >> 

操作，并且只能是其中 20 个操作的组合。此外，只能使用 int 变量，不能使用 if 语句、循环或函数调用。

Range(int x, int lower, int upper){
//... some code here
return retVal;
}

显然我明白这里的逻辑。 If((x >= lower) && (x <= upper)) 返回 1;唯一的问题是我无法使用 if 语句、<、>、== 或 &&。

Answer 1

您可以创建比较谓词 x < y (如果为 true，则返回 -1，如果为 false，则返回 0)如下所示:(请参阅 Hacker's Delight，第 2 章，子章比较谓词)

((x - y) ^ ((x ^ y) & ((x - y) ^ x))) >> 31;

您没有列出减法，但您可以模拟 x - y与 ~(~x + y)

使用其中两个谓词，使 1 & ~((x < lower) | (upper < x))

这显然假设 2 的补码负数和 32 位整数在溢出时换行。所以这不是可移植的，但这是这种技巧的常态。

<小时/>

根据要求，这使得总的事情:

int in_range(int x, int lower, int upper)
{
    int p = ((x - lower) ^ ((x ^ lower) & ((x - lower) ^ x))) >> 31;
    int q = ((upper - x) ^ ((upper ^ x) & ((upper - x) ^ upper))) >> 31;
    return 1 & ~(p | q);
}

它仍然有一些减法，如果你真的想要的话，替换它们是微不足道的。

使用 >= 可以让它稍微短一点。和<=谓词(也可以在 Hacker's Delight 中找到)。

这是我的网站，上面写着 correct .

<小时/>

这是一种使用较少运算的方法，请记住我们不能使用减法:

int p = (x | ~upper) & ((x ^ upper) | (~upper + x));
int q = (lower | ~x) & ((lower ^ x) | (~x + lower));
return 1 & ((p & q) >> 31);

它使用 <=来自 HD 的谓词，看起来像 (x | ~y) & ((x ^ y) | ~(y - x))以其纯粹的形式。

这是我的网站，上面写着 correct .