# Names of power-of-two bit operations on bitsets that would not assume any number interpretation

Three commonly used functions when it comes to bit manipulation are :

• is_pow2: Checking that an integer is a power-of-two (only one bit is set): $$00010000 \Rightarrow yes$$
• floor_pow2: Finds the largest integer power of two not greater than the given value $$00010010 \Rightarrow 00010000$$ (msb on the left, lsb on the right)
• ceil_pow2: Finds the smallest integer power of two not less than the given value $$00010010 \Rightarrow 00100000$$ (msb on the left, lsb on the right)

However, the concept of a power of two requires to assume a numeric interpretation of sets of bits. But fundamentally the functionality provided by these functions stay valid on bitsets without a numeric interpretation. For example, what is_pow2(x) is really asking is whether popcount(x) == 1. And popcount does not require to define any concept of power of two.

I was wondering if the three functions is_pow2, floor_pow2, ceil_pow2 had commonly accepted names in mathematics, computer science or computer engineering which do not rely on the concept of a power of two.

You can think of a bitvector as a set, by giving names to the various bits. For example, if we name the bits in an 8-bit integer using the numbers $$0,\ldots,7$$ (where $$0$$ is the LSB and $$7$$ is the MSB), then $$00010010$$ is the same as $$\{1,4\}$$.

Your first function asks whether the set has size $$1$$. If we name the bits using numbers as above, the second function is maximum and the third is minimum.

• I don't think the third function (ceil_pow2) corresponds to the least-significant set bit. It appears to be a left-shift of the most-significant set bit, so it'd be more like the max plus one (modulo whatever overflow logic was intended).
– mhum
Commented Nov 8, 2019 at 0:50