有人可以解释这个按位数组环绕表达式吗？

Question

我一直在研究 Diamond-square 算法，我遇到了 this website，它向我指出了 Notch 的 Minicraft 的源代码，并对 Notch 实现的算法进行了转换。

在大多数情况下，我理解该算法，但我可以理解这两个函数中的特定表达式：

private double sample(int x, int y) {
    return values[ (x & (w - 1)) + (y & (h - 1)) * w ];
}

private void setSample(int x, int y, double value) {
    values[ (x & (w - 1)) + (y & (h - 1)) * w ] = value;
}

我确实理解 x + y * w，但不理解 (x & (w - 1)) + (y & (h - 1)) * w，这篇文章除了说明它用于环绕之外没有解释这一点。

我在 python 中编码，但我认为 Java 的按位 & 和 python 之间没有任何区别，所以我摆弄了一下，但我仍然无法理解。我做的其中一件事是模拟不同的 x 和 y 值并将它们提供给该计算的循环：

import random
w = h = 257     # 2^8 + 1
for i in xrange(10):
    x = int(random.uniform(0, 1) *255)
    y = int(random.uniform(0, 1) *255)

    print x, y, '|', (x & (w-1)) + (y & (h-1)) *w

    # I used a less readable right-aligning version of the above to display the output:
    # print str( x ).rjust(3), str( y ).rjust(3), '|', str( (x & (w-1)) + (y & (h-1)) * w ).rjust(3)

输出：

112 213 |   0
181 117 |   0
  1 105 |   0
216 223 |   0
170 185 |   0
158  32 |   0
124 225 |   0
 62 153 |   0
 90 147 |   0
196  69 |   0

除非我在这里做一些根本性的错误，否则它总是给我零，除非 x and/or y 等于 w-1，在这种情况下：

256  15 |   256
 21 256 | 65792
256 256 | 66048

在实际算法中，x 和 y 的值似乎总是（如果我理解正确的话）介于 0 和 halfStep 之间，其中 halfStep = stepSize/2、stepSize = featureSise 似乎（在 Minicraft 的代码中）总是硬编码为 16 或 32。因此，根据我目前的理解，表达式的计算结果总是 0.

所以我很困惑。我不知道这有什么用，也不知道它在实践中是如何工作的……我知道它有效，但它看起来像魔法…… 我了解按位 & 的工作原理，但这似乎没有帮助。

Answer 1

w 和 h 必须是 2 的幂（分别表示 x 和 y 的局部边界）。然后，w-1 和 h-1 是 1 的序列。一个代表可能导致值分别低于 w 和 h（并且仍然是 >= 0）的每一位信息。

当您现在评估按位和 (&) 时，例如x & (w-1)，这实际上会产生 x % w，其中 % 是 python 中的 modulo 操作，用于 x >= 0。因此，如果 w > x >= 0 则 x 映射到 x，否则 x 被截断（将较高位清零），从而满足 w > x >= 0。这同样适用于 y 和 h.

因此，这些逻辑运算无非是mod的比特级计算。

对于您的代码：设置 w=h=256 一切都会成功。

有人可以解释这个按位数组环绕表达式吗？

Can someone explain this bitwise array-wrap-around expression?

python

algorithm

word-wrap