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

Question

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

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

! ~ & ^ | + << >> 

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

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

显然我理解这里的逻辑。如果((x >= 下) && (x <= 上)) 返回 1;唯一的问题是我不能使用 if 语句、<、>、== 或 &&。

Answer 1

你可以做比较谓词x < y (如果为真则返回 -1，如果为假则返回 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 .