Bilangan bulat logaritma basis 2 dalam O (1)

Seringkali perlu untuk menghitung seluruh bagian dari basis logaritma 2 dari bilangan bulat apa pun.



Keputusan langsung adalah membuat loop dan dalam loop ini terus-menerus membagi angka dengan dua hingga menjadi nol. Berapa banyak perpecahan seperti itu yang terjadi, seperti itulah nilai logaritma. Ya, metode ini berhasil dan memiliki hak untuk hidup, tetapi saya ingin menunjukkan bagaimana metode ini dapat dilakukan tanpa siklus dan struktur yang rumit.



Jadi, kami ingin menghitung rumus berikut:

$$

$$y = [log_2(x)], x - ,$$

Keputusan

Bagi yang tidak tertarik dengan penalarannya, saya akan langsung memberikan fungsi yang sudah jadi untuk menghitung logaritma:

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

Penjelasan

Pertama, mari kita ubah bilangan x menjadi notasi biner dengan panjang tertentu.



Misalnya, panjang = 8, tetapi tidak masalah dan panjang angkanya bisa berapa saja.



Sekarang ingat apa dasar terjemahan sebuah angka menjadi notasi biner. Untuk merepresentasikan bilangan sebagai penjumlahan dari dua pangkat dua. Angka derajat akan menentukan posisi bit, yaitu 1. Contoh:$$$45 = 32 + 8 + 4 + 1 = 2^5 + 2^3 + 2^2 + 2^0$... Itu. bilangan derajat 5, 3, 2 dan 0. Ini berarti bahwa bit ke-5, ke-3, ke-2, ke-0 sama dengan 1. Sisa bit di antara mereka sama dengan nol. Bit dimulai dari sisi kanan. Ternyata begitu$$$45_{10} = 101101_2$



Dapat dicatat bahwa terjemahan ke dalam notasi biner terkait erat dengan eksponen, dan logaritma adalah kebalikan dari eksponen dan sama dengan eksponen.

$$

$$2^y = x, y = log_2(x)$$

Selain itu, eksponen yang Anda butuhkan untuk menaikkan 2 adalah jumlah bit tunggal dalam notasi biner. Ternyata jika Anda menemukan jumlah bit tunggal, maka kita mendapatkan bagian integer dari nilai logaritma ke basis dua. Sebagai contoh, jika 32 = 100000, bit satu berada di urutan ke-5, jadi logaritma adalah 5.



Tetapi karena mungkin ada beberapa bit, bukan 1, pertanyaan akan muncul tentang bit mana yang harus diambil untuk menemukan logaritma. Jawabannya adalah bilangan dari bit terakhir, dimulai dari sisi kanan pencatatan bilangan, karena itu adalah pangkat dua tertinggi yang menentukan seluruh bagian logaritma, sisanya membentuk bagian pecahan dari logaritma.



Pertimbangkan contoh lain - angka$$$45_{10} = 101101_2$... Bit terakhir berada di tempat ke-5, jadi bagian bilangan bulat dari logaritma 45 adalah 5. dan memang$$$log_2(45)=5.4919$... Kami membuang bagian pecahan dan meninggalkan 5.



Ini juga berfungsi dengan nomor lain.



Hasilnya, kita mendapatkan bahwa bagian bilangan bulat dari logaritma sama dengan bilangan bit terakhir, dihitung dari kanan. Pertanyaan: bagaimana menemukan bilangan bit terakhir?



Untuk ini, ada fungsi berdasarkan operasi bitwise, yang saya temukan di buku oleh G. Warren "Trik algoritmik untuk programmer".

• Membulatkan ke bawah menjadi pangkat dua (atau menyoroti bit terakhir dalam notasi biner sebuah angka). Sebenarnya, Anda bisa membulatkannya, tetapi nilai logaritmanya juga akan dibulatkan.
• Menghitung jumlah bit tunggal dalam notasi biner sebuah bilangan

Kedua fungsi dijelaskan dengan baik di sana, dan saya memberikan kodenya sebelumnya.



Dengan menggunakan kedua fungsi tersebut, algoritma untuk menghitung algoritma tersebut adalah sebagai berikut:

1. Pilih bit terakhir di nomor tersebut. Sekarang jumlahnya menjadi 100000
2. Kurangi satu dari angka yang dihasilkan. Maka angkanya menjadi seperti ini: 011111
3. Hitung jumlah bit unit dan ini akan menjadi nilai integer dari logaritma

Situasi luar biasa

Logaritma memiliki situasi yang luar biasa ketika x = 0. Secara teori, algoritma seperti itu tidak ada (atau dalam batasnya sama dengan -∞). Namun, karena kita menyimpang sedikit dari hukum matematika dalam pemrograman, fungsi tersebut tetap berfungsi meskipun input fungsinya nol. Dalam hal ini, nilai logaritma adalah 32 (jika angkanya 32-bit). Ini karena fungsi pembulatan ke pangkat dua terdekat akan memberi 0, kemudian kita kurangi satu dari nol dan mendapatkan angka 0xFFFFFFFF, dan ada 32 unit di bilangan ini, jadi logaritmanya akan menjadi 32.



Ya, dari sudut pandang matematika, ini salah, tetapi ada beberapa kasus, bila berguna dari sudut pandang pemrograman.

Menghitung panjang kode biner

Tidak mungkin fungsi seperti itu akan digunakan untuk menghitung logaritma matematika, karena logaritma lebih sering dianggap dari bilangan real, bukan bilangan bulat.

Namun, dalam praktiknya, menghitung panjang kode biner adalah tugas yang lebih umum.



Biarkan kode biner dengan panjang tertentu diberikan. Ini bisa berupa, misalnya, jalur di pohon biner. Jika satu bit ditulis di depan kode ini, maka Anda dapat menghitung panjang kode ini tanpa menggunakan variabel tambahan dengan mengambil logaritma integer.



Sebagai contoh, berikan kode 0001110110 yang ditulis, misalnya, dalam sel 32 bit dan kita sering perlu membaca panjang kode ini. Untuk melakukan ini, tambahkan satu bit tambahan sebelum kode.



Kami mendapatkan: 10001110110. Dan sekarang kami dapat menghitung panjang kode ini dengan aman melalui logaritma integer, tanpa menyimpan panjang kode ini secara terpisah di tempat lain.



Jika kita mempertimbangkan panjang kode, di mana semua nol, maka fungsinya akan mengembalikan panjang = 32, yang mungkin salah, jadi situasi ini harus diramalkan. Dalam beberapa situasi, berguna jika fungsi mengembalikan 32, dan dalam situasi lain, misalnya, nol.

Sumber

1. G. Warren “Trik Algoritma untuk Pemrogram. Edisi revisi. ", 2004