4

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

4

3 回答 3

3

这可能无法回答您的问题，但您正在寻找的可能是这个。
这些是Sean Eron Anderson 编制的技巧，他甚至悬赏 10 美元奖励那些能找到一个 bug 的人。我在这里找到的最接近的东西是一个宏，它查找任何整数X是否有一个介于M和N之间的单词

确定一个单词是否有一个介于 m 和 n 之间的字节

当 m < n 时，该技术测试字 x 是否包含无符号字节值，例如 m < value < 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)
于 2012-04-07T06:07:13.473 回答
2

如果数字是有限的正整数，这是可能的。

假设我们有一个由(a1,b1)和表示的矩形(a2,b2)。给定一个点(x,y)，我们只需要计算表达式(a1<x) & (x<a2) & (b1<y) & (y<b2)。所以现在的问题是找到表达式c对应的位运算

设ci为数字的第 i 位c（可以通过掩码ci和位移获得）。我们证明，对于最多n位的数字，c<d等价于r_(n-1)，其中

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

证明：当cianddi不同时，左表达式可能为真（取决于((!ci)&di)），否则右表达式可能为真（取决于r_(i-1)下一位的比较）。

该表达式((!ci)&di)实际上相当于位比较ci < di。因此，这个递归关系返回真，它从左到右逐位比较，直到我们可以确定c小于d。

因此，比较运算符对应的是纯位运算表达式，因此可以通过纯位运算在矩形内找到一个点。

编辑：实际上不需要条件语句，只需扩展r_(n+1)，然后完成。

于 2012-04-07T06:51:53.950 回答
2

x,y 在矩形中，{x0<x<x1 and y0<y<y1}如果{x0<x and x<x1 and y0<y and 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。（== orequiv是一个位运算符，可以用 and/or/not 表示）

然而，我们需要某种方式将信息以一位到多位的方式传播。所以我们问自己这个问题：我们是否可以只使用“位”运算符来“编码”一个函数，这相当于if(q,k,a,b) = if q[k] then a else b. 答案是肯定的：

  • 我们创建了一个包含将 q[k] 复制到每个位上的位字。我可以想到两种方法来做到这一点：
    • 1）左移k，然后右移wordsize（有效，但仅当您有复制最后一位的移位运算符时才有效）
    • 2）效率低但理论上正确的方法：
      • 我们将 q 左移 k 位
      • 我们将这个结果and与 10000...0
      • 我们将其右移 1 位，并or使用非右移版本。这会将第一个位置的位复制到第二个位置。我们重复这个过程，直到整个字与第一位相同（例如 64 次）
  • 调用这个结果mask，我们的函数是(mask and a) or (!mask and b)：a如果第kth 位q为真，则结果为，否则为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

于 2012-04-07T06:34:22.953 回答