algorithm - 在 int 中找到第 n 个 SET 位

Question

我想找到 n 的位置，而不仅仅是最低的设置位th 最低设置位。 (我不是在谈论 n 位位置的值)

例如，假设我有:
0000 1101 1000 0100 1100 1000 1010 0000

我想找到设置的第 4 位。然后我希望它返回:
0000 0000 0000 0000 0100 0000 0000 0000

如果popcnt(v) < n , 如果这个函数返回 0 就有意义了，但我可以接受这种情况下的任何行为。

如果可能的话，我正在寻找比循环更快的东西。

Answer 1

如今，使用来自 BMI2 instruction set 的 PDEP 非常容易.这是带有一些示例的 64 位版本:

#include <cassert>
#include <cstdint>
#include <x86intrin.h>

inline uint64_t nthset(uint64_t x, unsigned n) {
    return _pdep_u64(1ULL << n, x);
}

int main() {
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 0) ==
                  0b0000'0000'0000'0000'0000'0000'0010'0000);
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 1) ==
                  0b0000'0000'0000'0000'0000'0000'1000'0000);
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 3) ==
                  0b0000'0000'0000'0000'0100'0000'0000'0000);
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 9) ==
                  0b0000'1000'0000'0000'0000'0000'0000'0000);
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 10) ==
                  0b0000'0000'0000'0000'0000'0000'0000'0000);
}

如果您只想要第 n 个设置位的(从零开始)索引，请添加尾随零计数。

inline unsigned nthset(uint64_t x, unsigned n) {
    return _tzcnt_u64(_pdep_u64(1ULL << n, x));
}