Bagaimana Mengira Log2 dengan Tepat untuk Nilai Integer dalam C?

Cara Betul untuk Mengira Log2 dalam C untuk Nilai Integer

Dalam C Standard Libraries hanya terdapat kaedah log untuk titik terapung. Walau bagaimanapun, kaedah log sering digunakan untuk mencari tahap indeks dalam pokok binari menggunakan lantai formula(2log(indeks)).

Pendekatan biasa ialah menggunakan int targetlevel = int(log(index)/log(2)). Tetapi pendekatan ini boleh membawa kepada ralat pembundaran untuk elemen tepi (elemen dengan nilai 2^n), mengakibatkan n-1.9999999999999 dan bukannya n.0 yang dijangka dikembalikan.

Penyelesaian untuk Pengiraan Log2 Tepat

Untuk membetulkan isu ini dan memastikan pengiraan log2 yang tepat untuk nilai integer, pendekatan yang lebih baik ialah menggunakan arahan bsr (bit scan reverse). bsr tersedia pada platform x86 dan x86-64 dan mengembalikan kedudukan bit set tertinggi dalam integer tidak bertanda. Ini bersamaan dengan log2() untuk integer positif.

Berikut ialah coretan kod C yang dioptimumkan yang memanfaatkan arahan 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;
}

Kod ini menggunakan ASM sebaris untuk menggunakan arahan bsr dengan cekap dan menyediakan pengiraan log2 yang tepat untuk integer.

Atas ialah kandungan terperinci Bagaimana Mengira Log2 dengan Tepat untuk Nilai Integer dalam C?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!