C- BitArray分割故障

Question

我目前正在尝试使用BITSet在C中实现eRatosthenes的筛子，但是当我试图筛选高达1,000,000（100万） - 虽然有100,000（1万）仍在工作，但我不知道为什么要获得SEG过失。

这是我使用的代码（我标记了错误的行）：

#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)));

进行分区和mod时，您需要将/mod除以 bits 的数量，而不是 bytes 的数量：：

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位的情况，请在上述代码中使用CHAR_BIT代替8。无论sizeof(uint64_t)评估什么都不重要，因为您仍然可以获得所需的适当数量。

Answer 2

您将x bytes 分配给 calloc，将总数除以sizeof（prime_t），但好像您有X Prime_t elements的空间。

编辑：或者实际上，您正在分配一个 1 元素的数组

如果您想按照现在的使用方式进行操作，则应该这样做：

calloc(X, sizeof(prime_t))而不是。

编辑：代码中的其他主要问题是您使用的是字节级索引而不是位级。

请注意，prime_t中有sizeof(prime_t) * 8位，因此，在每个字节中，您设置了精确1位，true。索引时，您除以sizeof(prime_t)而不是(sizeof(prime_t) * 8)。