C语言实现埃氏筛连续素数位数组，能否仅靠位移位跨int元素访问位

C语言与硬件层面都不支持仅靠对数组首元素的单次移位操作，访问连续内存块中跨存储单元的位。
从规则层面看：对N位的整数类型执行移位操作时，若移位计数大于等于操作数的位宽，程序行为属于C标准定义的未定义行为，不会自动将溢出的位关联到相邻的下一个内存单元。从硬件层面看：CPU的移位指令仅对单个寄存器内的位生效，寄存器和内存中的int存储单元一一对应，不存在“移位溢出的位自动写入相邻内存单元”的硬件逻辑，跨单元的位访问必然需要显式定位存储单元的下标。

比如你测试的A[0] & (1 << 32)写法：当A[0]是32位int类型时，移位32位的操作在绝大多数GCC实现中会直接返回0，根本不会和A[1]的内存位置产生任何关联，这也是你当前实现出现异常的核心原因。

• 移位操作的未定义行为：你写的state[0] | (1 << j)当j大于等于31时，移位计数已经超过32位int的位宽，操作结果完全不可控，既不会自动映射到state[1]的存储位置，还可能触发越界访问。
• 内存分配大小不匹配：你定义SIZE 1意味着只分配了1个32位int的空间，最多能标记32个自然数的状态，但MAX设为70，需要至少71位的存储容量，空间不足本身就会导致所有高位的标记操作完全失效。
• 端序误解：小端/大端的差异只影响多字节类型的字节存储顺序，不会改变单个int内部的位权映射，你跨单元访问位的问题和端序没有任何关系，不存在需要额外适配位序的场景。

你想避免显式除法、取模计算下标的需求完全可以实现——由于每个存储单元的位宽是固定的32位，计算下标的过程完全可以用位移和位与操作替代，没有任何除法指令的开销，甚至比你之前硬编码访问A[0]的写法效率更高：

• 定位位所在的数组单元：对n右移5位（等价于除以32，CPU单周期指令），得到对应的数组下标
• 定位位在单元内的偏移：对n和0x1F做位与（等价于模32，同样是单周期指令），得到单元内的移位计数

对应的操作可以封装成无开销的宏，使用体验和你预期的简化写法几乎一致：

// 读取第n位的状态
#define GET_BIT(arr, n)  (arr[(n) >> 5] & (1 << ((n) & 0x1F)))
// 将第n位置为1
#define SET_BIT(arr, n)  (arr[(n) >> 5] |= (1 << ((n) & 0x1F)))

使用时不需要手动计算下标，直接传入自然数n即可，比如：

// 初始化：根据MAX值计算需要的存储单元数量，向上取整到32位的倍数
#define MAX 70
#define SIZE ((MAX + 32) / 32)
int* state = calloc(SIZE, sizeof(int));

// 标记j为非素数，完全不需要手动写数组下标
SET_BIT(state, j);
// 读取i的素数状态
if (!GET_BIT(state, i)) {
    // i是素数
}

这种写法没有任何除法、取模运算，所有计算都是CPU级别的位操作，开销可以忽略不计，同时可以支持任意大的n值访问，不会出现移位超范围的问题。

• 不要尝试将数组首元素强转为更大位宽的整数类型来跨单元访问：比如把首元素指针强转为64位整数指针，这种写法存在严格的对齐要求，当内存块没有按64位边界对齐时，会直接触发总线错误，属于不可靠的未定义行为。
• 不要依赖编译器对超宽移位的特殊处理：不同编译器对移位超位宽的实现逻辑差异极大，有的会截断移位计数，有的会直接返回0，没有可移植性可言。
• 计算存储容量时不需要单独计算字节数：直接按32位为单位向上取整即可，比如MAX=70时，需要(70 + 32)/32 = 3个int单元，总共96位，足够覆盖所有自然数的状态标记。

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