java - 翻译这个Eratosthenes筛网的Java实现？

这是Java中的程序，通过将布尔数组存储为位数组来实现Sieve或Eratosthenes。我以前从未用Java编写过代码，但是总体思路很容易理解。但是，我不明白getBit和setBit函数如何工作？我猜想getBit函数会创建一个我将其设置为1的位掩码，并且掩码和数组之间是否按位AND？但是，我并不是很了解细节（例如，为什么我在作为索引传递给数组之前右移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);
}

最佳答案

提前注意事项：


(i >> 4)将i除以16，这是array中包含第i位的块（8位）的索引
(i >> 1)将i除以2
二进制代码中的7是111
((i >> 1) & 7)表示“ i / 2的最右边三位”，它是介于0和7之间（包括0和7）的数字
(1 << ((i >> 1) & 7))左移0至7次（00000001，00000010，...，10000000）。这是位掩码，用于设置/从所选块中获取感兴趣的位。


getBit(i)解释


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


setBit(i)解释


8位块和位掩码的计算等效于getBit
不同之处在于，按位或用于设置感兴趣的位。


编辑

第一个问题：


  现在几乎可以理解，您能否解释一下为什么我们能够通过向左移（（i >> 1）＆7）次来找到与数字i对应的位的位置？换句话说，我理解该操作在做什么，但是为什么这会给我们正确的位位置呢？


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

关于第二个问题：


  另外，为了澄清起见，在每次调用setBit之后将j增加2 * i的原因是因为我们只需要设置与i的奇数倍对应的位，对吗？


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


  另一种改进是最初仅列出奇数（3、5，...，n），并在步骤3中以2p的增量计数，因此仅标记p的奇数倍。


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

我希望这有帮助！