翻译这个 java 埃拉托色尼筛法的实现？

Question

这是 Java 中的一个程序，它通过将布尔数组存储为位数组来实现 Sieve 或 Eratosthenes。我以前从未在 Java 中编码过，但总体思路很容易理解。但是，我不明白 getBit 和 setBit 函数是如何工作的？我猜测 getBit 函数创建了一个位掩码 i 设置为 1 并在掩码和数组之间按位 AND ？但是，我并没有真正理解细节（例如，为什么 i 在作为索引传递给数组之前右移 4，以及为什么 MEMORY_SIZE 等于 MAX 右移 4)。请用文字解释 getBit 和 setBit 的每个步骤，如果可能的话，在 Python?

中的等效实现

private static final long MAX = 1000000000L;
private static final long SQRT_MAX = (long) Math.sqrt(MAX) + 1;
private static final int MEMORY_SIZE = (int) (MAX >> 4);
private static byte[] array = new byte[MEMORY_SIZE];
//--//
for (long i = 3; i < SQRT_MAX; i += 2) {
  if (!getBit(i)) {
    long j = (i * i);
    while (j < MAX) {
      setBit(j);
      j += (2 * i);
    }
  }
}
//--//
public static boolean getBit(long i) {
  byte block = array[(int) (i >> 4)];
  byte mask = (byte) (1 << ((i >> 1) & 7));
  return ((block & mask) != 0);
}

public static void setBit(long i) {
  int index = (int) (i >> 4);
  byte block = array[index];
  byte mask = (byte) (1 << ((i >> 1) & 7));
  array[index] = (byte) (block | mask);
}

Answer 1

提前注意事项：

(i >> 4) 将 i 除以 16，这是 array 中包含第 i 位的块（8 位）的索引
(i >> 1) 将 i 除以 2
7二进制码是111
((i >> 1) & 7)表示"the three rightmost bits of i / 2"，是0到7（含）之间的数字
(1 << ((i >> 1) & 7)) 向左移动 0 到 7 次（00000001、00000010、...、10000000）。这是 set/get 所选块中感兴趣的位的位掩码。

getBit(i)解释

第一行选择感兴趣的位所在的 8 位块（即 byte）。
第二行计算一个位掩码，正好设置了一个位。设置位的位置与 8 位块中感兴趣的位相同。
第三行使用按位与提取感兴趣的位，如果该位是 1，则返回 true。

setBit(i)解释

8位块和位掩码的计算等同于getBit
区别在于按位或用于设置感兴趣的位。

编辑

第一个问题：

It almost makes sense now, can you please explain why we are able to find the position of the bit cooresponding to the number i by shifting a bit left ((i >> 1) & 7) times? In other words, i understand what the operation is doing, but why does this give us the correct bit position?

我认为这是因为算法的优化性质。由于 i 以 2 为步长递增，因此使用一半的位就足够了（因为无论如何都会设置其他位）。因此，i 可以除以 2 来计算所需的位移位数。

关于你的第二个问题：

Also, just to clarify, the reason we increment j by 2*i after each call to setBit is because we only need to set the bits cooresponding to odd multiples of i, right?

是的，因为根据 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes:

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count in increments of 2p in step 3, thus marking only odd multiples of p.

您的算法从 3 开始，i 递增 2，并以 2*i 的增量计数。

希望对您有所帮助！

翻译这个 java 埃拉托色尼筛法的实现？

Translating this java implementation of Sieve of Eratosthenes?

java

bytearray

bitwise-operators