A handy method to verify if a number n
is a power of two (like 2, 4, 8, etc.) is to use the following test:
bool test = n & (n - 1) == 0;
This operation can be very efficient because it only involves subtraction, a bitwise AND, and a comparison. If this expression is evaluated to true
, then the number n
is indeed a power of two.
Another method uses the std::popcount
(population count) function, which is part of the C++20 standard library, test:
bool test = std::popcount(n) == 1; // (Since C++20)
This function counts the number of set bits (1s) in. If the hardware supports a popcount instruction (POPCNT), this function can be very fast.
In C++, you generally “pay for what you use”. For this test there is no use for counting.
What is the better method, in terms of efficiency?