汉明立方体顶点上的查询点

我有 N 个点，仅位于 D 维立方体的顶点上，其中 D 约为 3。

A vertex may not contain any point. So every point has coordinates in {0, 1}^D. I am only interested in query time, as long as the memory cost is reasonable ( not exponential in N for example :) ).

给定一个位于立方体顶点之一的查询和一个输入参数r，找到所有具有以下特征的顶点（即点）汉明距离 <= r与查询。

走什么路c++ /questions/tagged/c%2b%2b环境？

我正在考虑 kd 树，但我不确定并需要帮助，任何输入，即使是近似的，将不胜感激！自从汉明距离发挥作用时，按位操作应该会有所帮助（例如 XOR）。

有一个很好的 Bithack 可以从一个位掩码开始k位设置为按字典顺序排列的下一个排列 https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation，这意味着循环所有蒙版相当简单k位设置。将这些掩码与初始值进行异或运算，准确给出汉明距离处的所有值k远离它。

So for D尺寸，其中D小于 32（否则更改类型），

uint32_t limit = (1u << D) - 1;
for (int k = 1; k <= r; k++) {
    uint32_t diff = (1u << k) - 1;
    while (diff <= limit) {
        // v is the input vertex
        uint32_t vertex = v ^ diff;
        // use it
        diff = nextBitPermutation(diff);
    }
}

Where nextBitPermutation可以在 C++ 中实现为类似的东西（如果你有__builtin_ctz)

uint32_t nextBitPermutation(uint32_t v) {
    // see https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
    uint32_t t = v | (v - 1);
    return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
}

或者对于 MSVC（未测试）

uint32_t nextBitPermutation(uint32_t v) {
    // see https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
    uint32_t t = v | (v - 1);
    unsigned long tzc;
    _BitScanForward(&tzc, v); // v != 0 so the return value doesn't matter
    return (t + 1) | (((~t & -~t) - 1) >> (tzc + 1));
}

If D is really低、4或更低、旧popcnt-with-pshufb效果非常好，通常一切都排列得很好，如下所示：

uint16_t query(int vertex, int r, int8_t* validmask)
{
    // validmask should be array of 16 int8_t's,
    // 0 for a vertex that doesn't exist, -1 if it does
    __m128i valid = _mm_loadu_si128((__m128i*)validmask);
    __m128i t0 = _mm_set1_epi8(vertex);
    __m128i r0 = _mm_set1_epi8(r + 1);
    __m128i all =        _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
    __m128i popcnt_lut = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2,  2,  3,  2,  3,  3,  4);
    __m128i dist = _mm_shuffle_epi8(popcnt_lut, _mm_xor_si128(t0, all));
    __m128i close_enough = _mm_cmpgt_epi8(r0, dist);
    __m128i result = _mm_and_si128(close_enough, valid);
    return _mm_movemask_epi8(result);
}

这应该相当快；与上面的 bithack 相比更快（nextBitPermutation，相当重，在那里被大量使用），并且还与循环所有顶点并测试它们是否在范围内（即使使用内置popcnt，这自动需要至少 16 个周期，而上面的应该不需要，假设所有内容都被缓存，甚至永久地存储在寄存器中）。缺点是结果使用起来很烦人，因为它是哪些顶点既存在又在查询点范围内的掩码，而不是它们的列表。不过，它可以很好地结合对与点相关的数据进行一些处理。

当然，这也会缩小到 D=3，只要使 >= 8 的点都不有效即可。 D>4 可以类似地完成，但需要更多代码，而且由于这实际上是一个强力解决方案，仅由于并行性而速度很快，因此从根本上来说，D 中的速度会呈指数级下降。