使用位运算符检查一个点是否在矩形内

Question

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

- Luke Vo

Answer 1

这可能不是你要找的答案，但你需要的可能是这个。Sean Eron Anderson编写了这些技巧，并为那些能够发现单个错误的人提供了10美元的奖励。我在这里找到的最接近的东西是一个宏，可以找到任何整数X是否有一个word，它的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)

- Shiplu Mokaddim

Answer 2

如果x0<x且x<x1且y0<y且y<y1，则表示x,y在矩形{x0<x<x1和y0<y<y1}内。

如果我们可以使用位运算符模拟<，那么就可以继续进行。

什么是二进制中的<？考虑以下内容：

a: 0 0 0 0 1 1 0 1
b: 0 0 0 0 1 0 1 1

在上述情况中，a>b，因为它包含第一个值为1的位，而b中对应的为0。我们正在寻找最左边的一位，使得myBit!=otherBit。（==或equiv是按位运算符，可以用and/or/not表示）

然而，我们需要一种方式来将一位的信息传播到多位。所以我们问自己：能否仅使用“位”运算符编写与if(q,k,a,b) = if q[k] then a else b等效的函数。答案是可以的：

我们创建一个位字，其中每个位都重复q[k]。我可以想到两种方法来做到这一点：

1）左移k位，然后右移wordsize（有效，但仅在您拥有将最后一位复制的移位运算符时才起作用）

2）低效但理论上正确的方法：

我们将q左移k位

我们将此结果与10000…0进行and 我们将其向右移动1位，并将其与未右移的版本进行or。这将位于第一位置的位复制到第二位置。我们重复此过程，直到整个字与第一位相同（例如64次）

称此结果为mask，我们的函数为(mask and a) or (!mask and b)：如果q的第k位为true，则结果将为a，否则结果将为b 取位向量c=a!=b and a==1111..1 and b==0000..0，我们使用我们的if函数依次测试第一位是否为1，然后测试第二位是否为1，依此类推：

a<b := 
  if(c,0, 
    if(a,0, B_LESSTHAN_A, A_LESSTHAN_B), 
    if(c,1, 
      if(a,1, B_LESSTHAN_A, A_LESSTHAN_B), 
      if(c,2, 
        if(a,2, B_LESSTHAN_A, A_LESSTHAN_B), 
        if(c,3, 
          if(a,3, B_LESSTHAN_A, A_LESSTHAN_B), 
          if(...
                  if(c,64, 
                    if(a,64, B_LESSTHAN_A, A_LESSTHAN_B), 
                    A_EQUAL_B)
                  )
             ...)
        )
      )
    )
  )

这需要 wordsize 步骤。但是，如果使用递归定义的函数或固定点组合器（如果不允许使用递归），则可以将其写成3行。

然后我们只需将其转换为更大的函数：xMin<x and x<xMax and yMin<y and y<yMax。

- ninjagecko

---

你可以通过简单地循环比特并查找在A中设置而在B中未设置的第一个比特来使用更少的代码（不一定更有效）。 （如何确定一个数字是否小于另一个数字？您需要查找最重要的不同数字。在二进制中只有两个值，因此较小的数字将是从最高有效位开始具有零的第一个数字，而另一个数字具有一个一。 - podperson

@podperson：我认为这正是我的做法，就循环而言。也许我误解了你想传达的观点; 你有什么不同的建议吗？ - ninjagecko

我的意思是循环，而不是手动编写 :-) — 本质上，你已经展开了循环。 - podperson

@podperson：哦，我担心那个方法可能是不可用的，因此不能仅由“位运算符”组成，就像问题所要求的那样。但是，如果你指的是使用reduce或fold-right函数，那完全是合法的，尽管有些晦涩难懂。至少，我可以定义一个递归函数使一切变得简洁。感谢您指出这一点。 - ninjagecko

Answer 3

如果这个数字是一个有限正整数，那么就有可能实现。

Suppose we have a rectangle represented by the (a1,b1) and (a2,b2). Given a point (x,y), we only need to evaluate the expression (a1<x) & (x<a2) & (b1<y) & (y<b2). So the problems now is to find the corresponding bit operation for the expression c

Let ci be the i-th bit of the number c (which can be obtained by masking ci and bit shift). We prove that for numbers with at most n bit, c<d is equivalent to r_(n-1), where

r_i = ((ci^di) & ((!ci)&di))  |  (!(ci^di) & r_(i-1))

Prove: When the ci and di are different, the left expression might be true (depends on ((!ci)&di)), otherwise the right expression might be true (depends on r_(i-1) which is the comparison of next bit).

The expression ((!ci)&di) is actually equivalent to the bit comparison ci < di. Hence, this recursive relation return true that it compares the bit by bit from left to right until we can decide c is smaller than d.

Hence there is an purely bit operation expression corresponding to the comparison operator, and so it is possible to find a point inside a rectangle with pure bitwise operation.

Edit: There is actually no need for condition statement, just expands the r_(n+1), then done.

- unsym