在c二进制文件中,测试以查看数字是否在范围内

Question

这是我无法弄清楚的谜题的一部分.该功能有三个输入.第一个是int,第二个是下限,第三个是上限.我需要测试以查看第一个数字是否在包含的下限和上限范围内.

如果它在范围内则返回1,否则返回0.捕获是我只能使用

! ~ & ^ | + << >> 

操作,只有20个的组合.另外,只能使用int变量,而不能使用if语句,循环或函数调用.

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

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

Answer 1

您可以制作比较谓词x < y(如果为真则返回-1,如果为假则返回0),如下所示:(参见Hacker's Delight,第2章,子章节比较谓词)

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

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

使用其中两个谓词,make 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中找到),它可以缩短一点点.

这是我的网站说它是正确的.

这是一种使用较少操作的方法,请记住我们不能使用减法:

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))纯粹的形式.

这是我的网站说它是正确的.

Answer 2

我喜欢你的这些谜题！为此你会想要有类似的东西，

好吧，抽象一点，你需要有 2 个变量。

第一个变量（我们称之为 blarg）需要设置上限并添加翻转的 x。现在您需要向 blg 添加一个并翻转它。

你的第二个变量（我们称之为保持）会将 x 添加到翻转的下限；之后添加 1 来按住并翻转它。

将 blarg = 设置为 blarg 加hold；将 blarg 向右移动 31。并将其与 1 相与。

应该是你正在寻找的。