How to Calculate Integer Log2 Values in C Without a Dedicated Function?

Determining Integer Log2 Values in C

In C , performing integer log2 operations may encounter limitations due to the absence of a dedicated log2() function. This issue is encountered when using log to calculate the level of an index in a binary tree, where the result may be rounded down for edge elements (i.e., elements with values 2^n).

To mitigate this issue and ensure accurate log2 calculations, the bsr instruction can be employed. Available on recent x86 or x86-64 platforms, bsr returns the position of the highest set bit in an unsigned integer, which is equivalent to log2().

Here's a succinct C/C function that utilizes inline ASM to invoke bsr:

#include <stdint.h>

static inline uint32_t log2(const uint32_t x) {
  uint32_t y;
  asm ( "\tbsr %1, %0\n"
      : "=r"(y)
      : "r" (x)
  );
  return y;
}

By utilizing this function, integer log2 values can be accurately calculated for any unsigned integer input.

The above is the detailed content of How to Calculate Integer Log2 Values in C Without a Dedicated Function?. For more information, please follow other related articles on the PHP Chinese website!