1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – mhum Nov 8 '19 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.