小编Mat*_*ias的帖子

我即将实施Eratosthenes筛,并对筛阵有一个普遍的问题.

我现在已经实施了几次筛子(在C中),并且总是使用一组uint8_t(外<stdint.h>)作为筛子.这是非常低效的内存,因为每个数字都使用8位来筛选,即使一位应该足够.

我怎么会用C来解决这个问题呢？我需要一个位数组.我可以几乎创建任何类型的(阵列uint8_t,uint16_t,uint32_t,uint64_t),并与比特掩码等访问单个位

我应该选择哪种数据类型以及在没有性能损失的情况下应该使用哪些操作来访问这些位？

PS:我不认为这是一个重复的只是一个BitArray实现,因为它的问题是具体的关于埃拉托色尼的筛,因为它的主要性质必须是有效的(不仅在内存使用情况,但在访问).我在想,也许可以使用不同的技巧来使筛分过程更有效...

我正在开发一个项目,我需要一些项目.我正在uint64_t为bitset 使用一个数组.

我目前的问题是,无论何时我想设置或检查一下,我都需要做这样的操作:

uint64_t index = 42;
bArr[index/64] |= (((uint64_t)1)<<(index%64)); 

我可以重写师,并与一些聪明的模与和位位移操作为好,但我担心的演员1.我需要这个演员,因为否则它1被视为32位单元.如本示例所示 - 如果没有强制转换,则输出错误:

uint64_t bArr[4];                           // 256 bits 
bArr[0] = bArr[1] = bArr[2] = bArr[3] = 0;  // Set to 0

uint64_t i = 255;
bArr[i/64] = (bArr[i/64] | (((uint64_t)1)<<(i%64))); 

uint32_t i2;
for (i2 = 0; i2 < 256; i2++) {
  if ((bArr[i2/64] & (((uint64_t)1)<<(i2%64))) != 0) {
    printf("bArray[%" PRIu32 "] = 1\n", i2);
  }
}

我能以聪明的方式绕过这个演员吗？我当时认为表演可能会受到每次读/写的影响......