确定性洗牌方法：[0,N)整数唯一映射至同范围的实现需求

需求说明 #

需要实现一个shuffle_idx函数，满足：

• 输入为范围[0, N)的整数，N始终是2的幂
• 输出必须是[0, N)内的唯一整数（双射映射）
• 无需预先生成全量映射序列，可单独处理单个元素，保证确定性与唯一性
• 禁止仅使用常量移位取模的循环旋转作为变换逻辑

用户现有尝试 #

用户曾用哈希函数实现，但存在冲突问题：

size_t shuffle_idx(size_t idx, size_t N){
  size_t hash_v = (PRIME1 * idx) % PRIME2; // PRIME2 > N
  return hash_v % N;
}

同时提供了一种低效实现，虽满足确定性和唯一性，但需预生成整个映射表，性能不足：

size_t bad_shuffle_idx(size_t idx, size_t N){
  std::vector<size_t> map_idx(N);
  std::iota(map_idx.begin(), map_idx.end(), 0);
  std::mt19937 g(0); // 固定种子保证确定性
  std::shuffle(map_idx.begin(), map_idx.end(), g);  
  
  return map_idx[idx];
}

可行实现方案 #

方案1：基于乘法逆元的线性混淆

利用N是2的幂的特性，选择与2的幂互质的奇数作为乘数（奇数和2^{k互质，乘法在模2}k下是可逆的，保证双射）：

size_t shuffle_idx(size_t idx, size_t N){
    // 选用黄金比例相关的魔数0x9E3779B9，是奇数，与任意2的幂互质
    const size_t multiplier = 0x9E3779B9;
    // N是2的幂，(N-1)是掩码，等价于模N运算
    return (multiplier * idx) & (N - 1);
}

• 优势：实现极简，单元素O(1)处理，完全满足确定性和唯一性
• 原理：奇数乘数在模2^k下存在逆元，因此每个输入对应唯一输出，且覆盖整个[0,N)范围

方案2：简化Feistel网络变换

Feistel结构天生可逆，适合构造复杂的双射变换，避免线性变换的规律性：

size_t shuffle_idx(size_t idx, size_t N){
    if (N == 1) return 0;
    const size_t half = N / 2;
    const size_t mask = half - 1;
    // 拆分高低半部分（因为N是2的幂，直接位操作拆分）
    size_t left = idx & mask;
    size_t right = idx & half;
    
    // 简单可逆混淆：右半部分移到左位，左半部分与右半部分的混淆结果异或
    size_t new_left = right;
    size_t new_right = left ^ ((right * 0x9E3779B9) & mask);
    
    return new_left | new_right;
}

• 优势：变换逻辑更复杂，避免简单线性变换的可预测性，同样O(1)处理单元素
• 原理：Feistel网络的每一轮变换都可逆，因此整体映射是双射

方案3：位反转加异或混淆

先对输入的二进制位进行反转（本身是双射），再通过异或操作加入额外混淆，避免单纯位反转的规律性：

// 辅助函数：反转num的前bit_count位
size_t reverse_bits(size_t num, size_t bit_count){
    size_t result = 0;
    for (size_t i = 0; i < bit_count; ++i){
        result |= ((num >> i) & 1) << (bit_count - 1 - i);
    }
    return result;
}

size_t shuffle_idx(size_t idx, size_t N){
    // 计算N对应的二进制位数（因为N是2的幂）
    size_t bit_count = 0;
    size_t temp = N;
    while (temp >>= 1) ++bit_count;
    
    size_t reversed = reverse_bits(idx, bit_count);
    // 加入异或混淆，避免单纯位反转的可预测性
    return reversed ^ 0x55555555 ^ (idx >> 1);
}

• 优势：变换后的分布更均匀，无明显规律，满足双射要求

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