C - Eratosthenes 筛法 - BitField

Question

我即将实施 Sieve of Eratosthenes 并且有一个关于筛阵列的一般性问题。

我现在已经（在 C 语言中）多次实施筛子，并且总是使用 uint8_t 的数组（在 <stdint.h> 之外）作为筛子。这是非常低效的内存，因为每个要筛选的数字都使用 8 位，即使一位应该足够了。

我将如何在 C 中解决这个问题？我需要一个位数组。我几乎可以创建任何类型的数组（uint8_t、uint16_t、uint32_t、uint64_t）并使用位掩码等访问单个位

我应该选择哪种数据类型以及我应该使用哪些操作来访问位而不损失性能？

PS：我认为这不是 的副本，只是 一个 BitArray 实现，因为它的问题是关于埃拉托色尼筛法的，因为它是主要性质需要高效（不仅在内存使用方面，而且在访问方面）。我在想，也许可以使用不同的技巧来提高筛分过程的效率...

Answer 1

最大的原生类型（可能 uint64_t）往往表现最好。您可以将位掩码存储在数组中或通过移位在现场生成它们。与直觉相反，由于更好的 caching/memory 访问特性，现场生成可能表现更好。无论如何，最好以相当通用的方式开始编写代码（例如，如果您使用纯 C，则定义您的类型宏）然后测试不同的版本。

缓存（持久或非持久）您的某些结果也可能不是一个坏主意。

Answer 2

正如 Weather Vane 在他的评论中提到的，您可以通过仅考虑每隔一个数字来节省额外的 space，因为除了 2 之外的所有偶数都是非素数。

所以在你的位数组中，每个位代表一个奇数。

这是我几年前使用此技术所做的一个实现。

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <time.h>
#include <math.h>
#include <stdint.h>

uint8_t *num;
int count = 0;
FILE *primefile;

int main(int argc, char *argv[])
{
  int i,j,root;
  time_t t;

  if (argc>1) count=atoi(argv[1]);
  if (count < 100) {
    fprintf(stderr,"Invalid number\n");
    exit(1);
  }
  if ((num=calloc(count/16,1))==NULL) {
    perror("calloc failed");
    exit(1);
  }
  if ((primefile=fopen("primes.dat","w"))==NULL) {
    perror("Coundn't open primes.dat");
    exit(1);
  }
  t=time(NULL);
  printf("Start:\t%s",ctime(&t));
  root=floor(sqrt(count));
  // write 2 to the output file
  i=2;
  if (fwrite(&i,sizeof(i),1,primefile)==0) {
    perror("Couldn't write to primes.dat");
  }
  // process larger numbers
  for (i=3;i<count;i+=2) {
    if ((num[i>>4] & (1<<((i>>1)&7)))!=0) continue;
    if (fwrite(&i,sizeof(i),1,primefile)==0) {
      perror("Couldn't write to primes.dat");
    }
    if (i<root) {
      for (j=3*i;j<count;j+=2*i) {
        num[j>>4]|=(1<<((j>>1)&7));
      }
    }
  }
  t=time(NULL);
  printf("End:\t%s",ctime(&t));
  fclose(primefile);
  return 0;
}

这里，num是位数组，根据你搜索的上限动态分配。因此，如果您要查找最多 1000000000（10 亿）个素数，它会使用 64000000（6400 万）字节的内存。

关键表达式如下：

对于 "normal" 位数组：

设置位 i:

num[i>>3] |= (1<<(i&7);
// same as num[i/8] |= (1<<((i%8));

校验位i:

(num[i>>3] & (1<<(i&7))) != 0
// same as (num[i/8] & (1<<(i%8))) != 0

因为我们只跟踪每个其他数字，所以我们将 i 除以 2（或者等价地，右移 1：

num[i>>4] |= (1<<((i>>1)&7);
// same as num[(i/2)/8] |= (1<<(((i/2)%8));

(num[i>>4] & (1<<((i>>1)&7))) != 0
// same as (num[(i/2)/8] & (1<<((i/2)%8))) != 0

在上面的代码中，有一些微优化，其中除法和模数由 2 的幂替换为位移位和按位与掩码，但大多数编译器应该为您做这些。

C - Eratosthenes 筛法 - BitField

C - Sieve of Eratosthenes - BitField

c

arrays

sieve

sieve-of-eratosthenes

bit-fields