弹出最低有效位并返回索引的好方法？

Question

我是 C++ 的新手，我正在尝试编写一个函数来弹出最低有效位，然后 return 该位的索引。有没有办法在不创建临时变量的情况下做到这一点？

现在我有一个用于查找索引的函数和一个用于弹出位的函数，但我想将两者结合起来。

inline int LSB(uint64_t b) {
return int(_tzcnt_u64(b));
}

inline uint64_t popLSB(uint64_t b, int index) {
    return (b ^ (1ui64 << LSB(b)));
}

我唯一的想法是需要一个临时索引变量，感觉很糟糕。

int bestIdea(uint64_t *b) {
    int index = int(_tzcnt_u64(*b));
    *b ^= (1ui64 << index);
    return index;
}

有更好的方法吗？如果这段代码有任何其他不必要或愚蠢的地方，我很乐意接受建议，这是我的第一个项目，我几乎不确定任何部分。

Answer 1

使用临时变量没有错。然而，现代建筑 superscalar and out-of-order so to better adapt for them you should only use that for the return value and don't use it to clear the least significant bit to avoid an unnecessary dependency chain

int popLsbAndReturnIndex(uint64_t *b) {
    int index = int(_tzcnt_u64(*b));
    *b &= *b - 1; // Not depend on the previous line
    return index;
}

现在我们有更好的 instruction-level parallelism 并且正文中的 2 行可以运行并行

当然一些真正聪明的编译器可以识别模式并将你的原始代码编译成没有依赖的版本，但没有人能保证

更多建议：

如果您有 C++20 或更高版本，请使用 std::countr_zero 而不是 _tzcnt_u64
使用引用而不是指针

结果是这样的

int bestIdea(uint64_t &b) {
    auto index = std::countr_zero(*b);
    b &= b - 1;
    return index;
}

弹出最低有效位并返回索引的好方法？

Good way of popping the least signifigant bit and returning the index?

c++

bit-manipulation

bitwise-operators