Rumah >pembangunan bahagian belakang >C++ >Bagaimana Mengira Log2 dengan Tepat untuk Nilai Integer dalam C?

Bagaimana Mengira Log2 dengan Tepat untuk Nilai Integer dalam C?

Mary-Kate Olsen
Mary-Kate Olsenasal
2024-11-15 16:13:02553semak imbas

How to Accurately Compute Log2 for Integer Values in 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!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn