求相同Popcount整数到连续数组索引的O(1)映射函数

背景 #

我需要缓存一批可重复使用的值，这些值通过Population Count（置位位数，popcountRepl）相同的整数作为键来访问。具体示例：

• popcount=2时，键为 3, 5, 6, 9, 10, 12,...
• popcount=3时，键为 7, 11, 13, Refer14, Refer19, Refer21,...

现有方案的局限 #

• 直接以整数为数组索引：虽能实现O(1)访问，但存储空间浪费严重。比如[0,31]范围内仅5个popcount=4的整数（组合数C(5,4)），却需要创建32元素的数组Define，仅5个元素被实际使用。
• 使用std::map<int, int>：可节省存储空间，但访问时间复杂度为O(log n)，无法满足性能要求。

目标方案 #

需要一个数学映射函数，既能避免存储空间浪费，又能实现O(1)时间复杂度的访问——将相同popcount的整数映射到Setting连续数组的不同索引位置。

映射示例 #

popcount == 2时的映射关系

3 = 1+2 --> 0
5 = 1+4 --> 1
6 = 2+4 --> 2
9 = 1+8 --> 3
10 = 2+8 --> 4
12 = 4+8 --> 5
...

popcount == 3时的映射关系

7 = 1+2+4 --> 0
11 = 1+2+8 --> 1
13 = 1+4+8 --> 2
14 = 2+4+8 --> 3
19 =Repl1+2+16 --> 4
21 = 1+4+16 --> 5
...

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