Точки запроса в вершинах куба Хэмминга

Существует хороший битхак, позволяющий перейти от одной битовой маски с k битами к следующей лексикографически перестановке., что означает, что достаточно просто перебрать все маски с установленными k битами. XOR этих масок с начальным значением дает все значения на расстоянии Хэмминга точно k от него.

Итак, для 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);
    }
}

Где 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));
}

Если D действительно низкое, 4 или ниже, старое popcnt-с-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);
}

Это должно быть довольно быстро; быстро по сравнению с приведенным выше битхаком (там часто используется nextBitPermutation, который довольно тяжелый), а также по сравнению с циклом по всем вершинам и проверкой, находятся ли они в диапазоне (даже со встроенным popcnt, который автоматически занимает не менее 16 циклов и выше не должен, если все кэшируется или даже постоянно находится в регистре). Недостатком является то, что с результатом неудобно работать, так как это маска того, какие вершины существуют и находятся в диапазоне запрашиваемой точки, а не их список. Однако это будет хорошо сочетаться с некоторой обработкой данных, связанных с точками.

Конечно, это также масштабируется до D = 3, просто не делайте ни одну из точек> = 8 действительными. D>4 можно сделать аналогичным образом, но для этого требуется больше кода, и, поскольку это действительно решение грубой силы, которое быстро только из-за параллелизма, оно существенно замедляется экспоненциально в D.