问询C语言并行埃氏筛代码中位操作语句及a[i/64]的含义

这段代码的核心是用位压缩存储节省内存——用uint_fast64_t类型的数组a，每个元素占64位，每一位对应一个数是否为素数的标记（1表示是素数，0表示非素数）。下面逐行解释你疑惑的代码：

第一行：判断当前数是否为素数 #

if (!(a[i / 64] & ((uint_fast64_t)1 << (i % 64))))       
    continue;

• i / 64：计算数字i对应的位落在数组a的第几个元素里（每个元素能存64个数的状态）。比如i=65时，65/64=1，对应a[1]这个元素。
• i % 64：计算i在对应数组元素的具体位置。比如i=65时，65%64=1，对应a[1]的第1位。
• (uint_fast64_t)1 << (i % 64)：生成一个64位掩码，只有i对应的那一位是1，其余位为0。
• 整个a[i/64] & 掩码的作用是检查i对应的位是否为1：如果结果为0，说明i已被标记为非素数，直接跳过后续筛除操作。

第二行：标记当前数为非素数 #

a[j / 64] &= ~(((uint_fast64_t)1) << (j % 64));

• ~(((uint_fast64_t)1) << (j % 64))：生成一个掩码，只有j对应的那一位是0，其余位为1。
• a[j/64] &= 掩码：把数组中j对应的位设为0，标记j为非素数（因为j是当前素数i的倍数）。

补充：初始化的意义 #

代码开头的a[i] = 0xAAAAAAAAAAAAAAAA;是初始化筛子状态：这个十六进制值的二进制是10101010...重复，即所有奇数对应的位为1（默认奇数可能是素数），偶数对应的位为0（除了2，所有偶数都不是素数），完全符合埃氏筛的初始逻辑。

内容的提问来源于stack exchange，提问作者glockutc