I am new to c and I'm trying to write a function that will pop the least significant bit and then return the index of that bit. Is there a way to do this without creating a temporary variable?

Right now I have a function for finding the index and one for popping the bit but I'd like to combine the two.

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)));
}

My only idea requires a temporary index variable which just feels bad.

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

Is there a better way of doing this? And if there is anything else not necessary or dumb about this code I'm happy to take suggestions, this is my first project and I'm not sure about pretty much any part.

CodePudding user response：

There's nothing wrong with using a temporary variable. However modern architectures are 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;
}

Now we have better instruction-level parallelism and the 2 lines in the body can run in parallel

Of course some really smart compilers can recognize the pattern and compile your original code to the version without dependency, but no one can guarantee that

Some more recommendations:

• Use std::countr_zero instead of _tzcnt_u64 if you have C 20 or higher
• Use references instead of pointers

The result is like this

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