Builtin Bit Functions

GCC builtins

Function	Returns	For long long
__builtin_popcount(x)	number of set bits	__builtin_popcountll
__builtin_clz(x)	leading zeros	__builtin_clzll
__builtin_ctz(x)	trailing zeros	__builtin_ctzll
__builtin_ffs(x)	index of the lowest set bit, 1-based (0 if $x=0$)	__builtin_ffsll
__builtin_parity(x)	popcount mod 2	__builtin_parityll
__lg(x)	$\lfloor {\log }_{2}x\rfloor$	works for both
__builtin_bswap32/64(x)	byte swap

clz and ctz are undefined at zero

__builtin_clz(0) and __builtin_ctz(0) produce garbage, not 32. Always guard:

int highBit(unsigned x) { return x ? 31 - __builtin_clz(x) : -1; }

This is one of the most common sources of “works locally, fails on the judge” bugs, because the behaviour differs between compilers and optimisation levels.

C++20 <bit> — portable and safe

#include <bit>
 
std::popcount(x)         // set bits
std::countl_zero(x)      // leading zeros   — well-defined at 0
std::countr_zero(x)      // trailing zeros  — well-defined at 0
std::countl_one(x)
std::countr_one(x)
std::bit_width(x)        // number of bits needed = floor(log2(x)) + 1
std::bit_floor(x)        // largest power of 2 <= x
std::bit_ceil(x)         // smallest power of 2 >= x
std::has_single_bit(x)   // is x a power of two
std::rotl(x, n)          // rotate left
std::rotr(x, n)          // rotate right
std::bit_cast<To>(x)     // reinterpret the bits, safely

All require unsigned arguments. Prefer these when C++20 is available: they are defined at zero, portable, and compile to the same instructions.

Performance

On any modern x86-64 CPU, popcount, clz and ctz are single instructions (POPCNT, LZCNT, TZCNT) — but only if the compiler is allowed to emit them.

#pragma GCC target("popcnt")                  // or "avx2", or "arch=haswell"

Without the target pragma, GCC falls back to a table-based or loop-based implementation that is 5-10× slower. On Codeforces, adding #pragma GCC target("popcnt") at the top of the file is a free speedup for popcount-heavy code.

Manual implementations

For when builtins are unavailable, or to understand what they do:

int popcount(unsigned x) {                    // parallel bit counting
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    return (x * 0x01010101) >> 24;
}
 
int ctz(unsigned x) {                         // de Bruijn multiplication
    static const int tab[32] = {0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,
                                31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9};
    return tab[((x & -x) * 0x077CB531u) >> 27];
}

The popcount routine is the classic “SWAR” (SIMD within a register) algorithm: count in pairs, then nibbles, then bytes, then sum the bytes with one multiplication.

std::bitset

bitset<1000> b;
b.count()                 // popcount, O(n/64)
b._Find_first()           // index of the first set bit (GCC extension)
b._Find_next(i)           // index of the next set bit after i
b.set(); b.reset(); b.flip();
b <<= k; b |= other;      // O(n/64)
b.any(); b.none(); b.all();
b.to_ullong();

_Find_first and _Find_next are GCC extensions but universally available on contest judges. They make iterating a sparse bitset $O(\text{set bits}\cdot n/64)$ rather than $O(n)$:

for (int i = b._Find_first(); i < (int)b.size(); i = b._Find_next(i)) { /* ... */ }

See Bitset Optimization.

Practical recipes

// iterate set bits
for (unsigned t = x; t; t &= t - 1) { int i = __builtin_ctz(t); /* ... */ }
 
// next permutation of bits with the same popcount (Gosper's hack)
unsigned nextSameCount(unsigned v) {
    unsigned c = v & -v, r = v + c;
    return r | (((v ^ r) >> 2) / c);
}
 
// all k-subsets of an n-set, in increasing order
for (unsigned v = (1u << k) - 1; v < (1u << n); v = nextSameCount(v)) { /* ... */ }

Gosper’s hack enumerates all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of size $k$ in $O(1)$ per subset — the right tool when a bitmask DP only needs masks of a fixed popcount.

See also: Bit Operations · Bitset Optimization · Constant Factor Optimization