efficient C++ subset impl with pop_lsb() using ctz compiler intrinsics for MSVC, GCC and Clang.

bitsubset.cpp

#include <vector>
#include <cassert>
#include <cmath>
#include <iostream>

#if defined _MSC_VER
// include MSVC compiler intrinsics
// for _BitScanForward
#include <intrin.h>

// https://learn.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64?view=msvc-170
// https://www.felixcloutier.com/x86/bsf
#pragma intrinsic(_BitScanForward)
#endif


// pops least significant bit from `bits` and 
// returns its index. Uses ctz compiler intrinsics
// to count trailing zeros. Supported compilers are 
// MSVC, GCC and Clang. Do not pass 0, will lead to 
// UB or out-of-bounds index.
unsigned int pop_lsb(unsigned int &bits) {
    // __builtin_ctz(0) is UB
    // _BitScanForward(0) results in out-of-bounds index
    assert(bits != 0);
#if defined __GNUC__ || defined __clang__
    // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#:~:text=in%20Function%3A%20int-,__builtin_ctz,-(unsigned%20int%20x
    // https://clang.llvm.org/docs/LanguageExtensions.html#:~:text=__builtin_clzs-,__builtin_ctz,-__builtin_ctzl
    unsigned int b = __builtin_ctz(bits);
#elif defined _MSC_VER
    unsigned long b;
    _BitScanForward(&b, bits);
#endif
    bits &= bits - 1;
    return b;
}

int main() {
    // number or elements to subset
    std::vector<int> elements {10, 2, 5};

    for (unsigned int i = 0; i < pow(2, elements.size()); i++) {
        unsigned int bits = i;
        std::cout << "( ";
        while (bits) {
            // every iteration here is an index to the original data structure
            std::cout << elements[pop_lsb(bits)] << " ";
        }
        std::cout << ")" << std::endl;
    }
}