如何在 C 中準確計算整數值的 Log2 ？

Correct Way to Compute Log2 in C++ for Integer Values

In C++ Standard Libraries there is only the log method for floating point. However, the log method is often used to find the level of an index in a binary tree using the formula floor(2log(index)).

A common approach is to use int targetlevel = int(log(index)/log(2)). But this approach can lead to rounding errors for edge elements (elements with value 2^n), resulting in n-1.999999999999 instead of the expected n.0 being returned.

Solution for Accurate Log2 Computation

To fix this issue and ensure accurate log2 computation for integer values, a better approach is to utilize the bsr (bit scan reverse) instruction. bsr is available on x86 and x86-64 platforms and returns the position of the highest set bit in an unsigned integer. This is equivalent to log2() for positive integers.

Here's an optimized C++ code snippet that leverages the bsr instruction:

#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;
}

This code uses inline ASM to invoke the bsr instruction efficiently and provides precise log2 computations for integers.

以上是如何在 C 中準確計算整數值的 Log2 ？的詳細內容。更多資訊請關注PHP中文網其他相關文章！