Hackerrank Bit Array解决方案疑问：insert函数与mask数组设计原理

题目背景 #

这是Hackerrank上的一道免费题目：给定四个整数N、S、P、Q，按照以下伪代码生成序列a：

a[0] = S (modulo 2^31)
for i = 1 to N-1
    a[i] = a[i-1]*P+Q (modulo 2^31) 

任务是计算序列a中不同整数的数量。

对方案中位掩码实现的疑问 #

我在分析该题的一个可行方案时，对其中的insert()函数原理完全摸不着头脑，代码如下：

unsigned long long mask[40000000];

unsigned insert(unsigned x) {
    unsigned res = (mask[x >> 6] & (1ULL << (x & 0x3F))) == 0;
    mask[x >> 6] |= 1ULL << (x & 0x3F);
    return res;
}

我的疑问点：

• 看起来mask数组是用来记录已出现的X值，但为什么右移6位后多个不同X会映射到同一个mask元素？
• 6位（对应0x3F即0b111111）有什么特殊意义？
• 这是不是一种实用的编程技巧？

位掩码技巧的原理解析 #

这是一种基于位的标记技巧，核心是用单个整数的二进制位来记录多个值的存在状态，以此大幅节省内存：

1. 6位的特殊意义
   代码里用的是unsigned long long类型，它在绝大多数系统中是64位（刚好是2的6次方）。x & 0x3F是取x的低6位，结果范围是0~63，刚好对应64位整数的每一个二进制位的位置——每一位都可以用来标记一个值是否出现过。

2. 不同X映射到同一mask元素的逻辑

   • x >> 6相当于把x除以64（整数除法），得到的结果就是该值在mask数组中的索引。也就是说，每64个连续的x值会共享同一个mask数组元素。
   • 对于每个x，用低6位确定要操作mask[index]中的哪一位：1ULL << (x & 0x3F)会生成一个只有对应位为1的64位整数。
   • 函数先检查该位是否为0（表示x从未出现过），然后将该位设为1（标记x已出现），返回的res用来统计新增的不同元素数量——返回1就说明这是一个新元素，返回0则说明已经存在过。

3. 内存优化的核心优势
   题目中x的范围是mod 2^31，也就是0~2^{31-1。如果用普通的布尔数组标记，需要2}31个字节（约2GB），这显然超出了大多数程序的内存限制。而用这种位掩码方式，只需要2^31 / 64 = 33554432个unsigned long long元素，每个元素8字节，总内存约268MB，完全在合理范围内（代码里开了40000000个元素，是预留了一点冗余空间）。

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