C - BitArray 段错误

Question

我目前正在尝试使用 BitSet 在 C 中实现埃拉托色尼筛法，但是当我尝试筛选高达 1,000,000(100 万)- 100,000(100,000)的素数时，我遇到了段错误虽然我不明白为什么会出现段错误。

这是我使用的代码(我标记了发生错误的行):

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

void eSieve(uint64_t upperLimit);
int main(int argc, char *argv[]) {
  uint64_t upperLimit;

  if (argc == 2) {
    upperLimit = (uint64_t) atoll(argv[1]);
    printf("Using custom limit: %" PRIu64 "\n", upperLimit);
  } else {
    upperLimit = 1000;
    printf("Using default limit: %" PRIu64 "\n", upperLimit);
  }

  eSieve(upperLimit);

  return 0;
}

typedef uint32_t prime_t;

void eSieve(uint64_t upperLimit) {
  if (upperLimit < 2) {
    printf("FAILURE: Bad upper limit.\n");
    return;
  }

  prime_t *sieve = calloc(1, (upperLimit + sizeof(prime_t) - 1)/sizeof(prime_t));

  if (!sieve) {
    printf("FAILURE: Could not initialize sieve.\n");
    return;
  }

  sieve[0] |= 3;    // Set first and second bit (representing 0 and 1)

  uint64_t prime, number;
  for (prime = 2; prime * prime < upperLimit; ) {
    for (number = prime * prime; number < upperLimit; number += prime) {
      // Segmentation fault for prime = 2 and number = 258048
      sieve[number/sizeof(prime_t)] |= (((prime_t) 1) << (number % sizeof(prime_t)));
    }

    while ((sieve[++prime/sizeof(prime_t)] & (prime_t)1 << (prime % sizeof(prime_t))) != 0)
      ;
  }

  number = upperLimit;
  while ((sieve[--number/sizeof(prime_t)] & (((prime_t)1) << (number % sizeof(prime_t)))) != 0)
    ;

  printf("Greatest prime-number below %" PRIu64 ": %" PRIu64 "\n", 
      upperLimit, number);
}

有人知道为什么会发生错误吗？我猜现在分配了足够的空间(不知何故)，但我现在看不出这是怎么可能的......

Answer 1

您没有得到正确的位数:

sieve[number/sizeof(prime_t)] |= (((prime_t) 1) << (number % sizeof(prime_t)));

当你做除法和取模时，你需要除法/取模的是位数，而不是字节数:

sieve[number/(sizeof(prime_t)*8)] |= (((prime_t) 1) << (number % (sizeof(prime_t)*8)));

类似地:

while ((sieve[++prime/(sizeof(prime_t)*8)] & (prime_t)1 << (prime % (sizeof(prime_t)*8))) != 0)

...

while ((sieve[--number/(sizeof(prime_t)*8)] & (((prime_t)1) << (number % (sizeof(prime_t)*8)))) != 0)

编辑:

您也没有分配正确的内存量。您需要的字节数等于限制除以位数，再加上 1 sizeof(prime_t) 以进行舍入。

prime_t *sieve = calloc(1, (upperLimit / 8) + sizeof(prime_t));

就目前而言，您正在分配所需字节的两倍。

此外，如果您想防止一个字节中有 8 位以上或少于 8 位的情况，请在上面的代码中使用 CHAR_BIT 代替 8。无论 sizeof(uint64_t) 的计算结果如何都无关紧要，因为您仍会获得所需的正确位数。