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

Question

这是一个 Java 程序，它通过将 boolean 数组存储为位数组来实现 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 中 block 的索引(8 位)包含 i第-位
• (i >> 1)划分 i由 2
• 7二进制代码是111
• ((i >> 1) & 7)表示“i / 2 最右边的三位”，这是一个介于 0 和 7(含)之间的数字
• (1 << ((i >> 1) & 7))向左移动了 0 到 7 次( 00000001 , 00000010 , ..., 10000000 )。这是用于设置/获取所选 block 中感兴趣的位的位掩码。

getBit(i)解释

1. 第一行选择感兴趣的位所在的 8 位 block (即 byte)。
2. 第二行计算一个位掩码，其中正好设置了一个位。设置位的位置与 8 位 block 中感兴趣的位相同。
3. 第三行使用按位与提取感兴趣的位，返回 true如果这个位是 1 .

setBit(i)解释

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

编辑

第一个问题:

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 的增量计数.

希望对您有所帮助!