• __builtin_popcount(x) and its long long variant __builtin_popcountll(x) return the number of set bits in x . Its function name is a contraction of "population count".
  • x > 0 && __builtin_popcount(x) == 1 determines if x is a power of 2. (see (x & (x - 1)) for another method)
• __builtin_clz(x) and its long long variant return the number of leading zero bits in x . Its function name is an acronym for "count leading zeros".
  • 1 << (32 - __builtin_clz(x)) finds the smallest power of 2 that is not smaller than x.
• __builtin_ctz(x) and its long long variant return the number of trailing zero bits in x . Its function name is an acronym for "count trailing zeros".
  • 1 << __builtin_clz(x) finds the greatest power of 2 that is a divisor of x.
• x & (x - 1) unsets the smallest set bit of x .
  • x > 0 && (x & (x - 1)) == 0 determines if x is a power of 2. (see __builtin_popcount(x) for another method)

Bitset

_Find_first() returns the first set bit
_Find_next(int idx) returns the next set bit