Bagaimanakah kita dapat menentukan dengan cekap sama ada nombor adalah kuasa 2?

Tentukan sama ada beberapa nombor adalah 2

Penerangan Masalah

Tentukan sama ada nombor yang diberikan adalah kuasa 2, yang memerlukan algoritma yang mudah dan tepat. Penulis mencadangkan dua algoritma, tetapi menghadapi masalah apabila menggunakan pengiraan nombor.

Algoritma pertama

Algoritma pertama Gunakan kitaran mudah untuk memeriksa kuasa 2 melalui anjakan:

Kaedah ini mudah dan mudah difahami, dan ia boleh berjalan dengan sempurna untuk sebarang nilai IsPowerOfTwo.

<code class="language-c#">private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}</code>

Algoritma kedua

ulong

Algoritma kedua bergantung pada pengiraan nombor:

Walau bagaimanapun, disebabkan oleh masalah membuang, algoritma ini tidak boleh dikendalikan dengan betul 9223372036854775809.

Algoritma yang lebih baik

IsPowerOfTwo_2

<code class="language-c#">private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}</code>

Penjelasan algoritma

Algoritma yang lebih baik ini dengan bijak menggunakan operasi bit:

operator bit Periksa sama ada kedua -dua bit kedudukan yang sepadan adalah 1.

<code class="language-c#">bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}</code>

tolak 1 dari nombor untuk menghidupkan semua 1 hingga 0, dan putar semua 0 hingga 1. Jika nombor adalah kuasa 2, binari menunjukkan bahawa hanya akan ada satu digit.

Apabila nombor dan (x -1) dilakukan dan operasi, semua bit kecuali 1 di sebelah kanan akan menjadi 0.

Oleh itu, jika hasilnya adalah 0, nombornya adalah kuasa 2.

• & Keluarkan sifar
• Untuk menghapuskan sifar (sifar -not -tidak dianggap kuasa ialah 2), syarat tambahan
.

Atas ialah kandungan terperinci Bagaimanakah kita dapat menentukan dengan cekap sama ada nombor adalah kuasa 2?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!