通过位运算符检查点是否在矩形内(Check whether a point is inside a rectangle by bit operator)

通过位运算符检查点是否在矩形内(Check whether a point is inside a rectangle by bit operator)

几天前，我的老师告诉我，可以仅使用位运算符检查给定点是否在给定矩形内。 这是真的吗？ 如果是这样，我该怎么办？

Days ago, my teacher told me it was possible to check if a given point is inside a given rectangle using only bit operators. Is it true? If so, how can I do that?

最满意答案

这可能无法解答您的问题，但您正在寻找的可能是这个。 这些是 Sean Eron Anderson编写的技巧 ，他甚至为那些能找到一个bug的人提供了10美元的奖金。 我在这里找到的最接近的是一个宏，它可以找出任何整数X是否有一个介于M和N之间的单词

确定一个字是否在m和n之间有一个字节

当m <n时，该技术测试字x是否包含无符号字节值，使得m <值<n。 当n和m为常数时，它使用7次算术/逻辑运算。 注意：等于n的字节可以通过可能在误报之间报告，因此如果需要某个结果，应该按字符检查。

要求：x> = 0; 0 <= M <= 127; 0 <= N <= 128

#define likelyhasbetween(x,m,n) \ ((((x)-~0UL/255*(n))&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)

该技术适用于快速预测试。 一个变量需要多一次操作（常量m和n总共8个），但提供的确切答案是：

#define hasbetween(x,m,n) \ ((~0UL/255*(127+(n))-((x)&~0UL/255*127)&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)

This might not answer your question but what you are looking for could be this. These are the tricks compiled by Sean Eron Anderson and he even put a bounty of $10 for those who can find a single bug. The closest thing I found here is a macro that finds if any integer X has a word which is between M and N

Determine if a word has a byte between m and n

When m < n, this technique tests if a word x contains an unsigned byte value, such that m < value < n. It uses 7 arithmetic/logical operations when n and m are constant. Note: Bytes that equal n can be reported by likelyhasbetween as false positives, so this should be checked by character if a certain result is needed.

Requirements: x>=0; 0<=m<=127; 0<=n<=128

#define likelyhasbetween(x,m,n) \ ((((x)-~0UL/255*(n))&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)

This technique would be suitable for a fast pretest. A variation that takes one more operation (8 total for constant m and n) but provides the exact answer is:

#define hasbetween(x,m,n) \ ((~0UL/255*(127+(n))-((x)&~0UL/255*127)&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)