Adakah nombor kuasa 2? Bagaimanakah kita dapat menentukan ini dengan cekap?

sama ada bilangan angka adalah 2 adalah kuasa 2

pernyataan soalan

Dalam sains komputer, masalah biasa adalah untuk menentukan sama ada nombor yang diberikan adalah kuasa 2. Masalah ini terutama dalam analisis algoritma dan algoritma. Algoritma ini harus mempunyai ciri -ciri berikut:

Kod ini mudah dan jelas.

1. boleh mengendalikan nilai integer lama yang tidak ditandatangani dengan tepat.
kaedah

Kaedah 1: Kaedah model shigging

Kaedah untuk menyelesaikan masalah ini adalah untuk melancarkan 2 kuasa berterusan, periksa sama ada kuasa -dalam -satu sepadan dengan nombor input. Ini boleh dilaksanakan seperti berikut: Kaedah 2: Bilangan algoritma pengiraan

Kaedah lain melibatkan pengiraan penggunaan bilangan pasangan. Walau bagaimanapun, ini memerlukan berhati -hati kerana pengiraan terapung boleh menyebabkan ketepatan. Pertimbangkan kod berikut:

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

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

Penyelesaian Optimal: Kaedah Pengkomputeran Bit Penyelesaian yang lebih berkesan adalah penggunaan operasi bit. Kuasa 2 mempunyai ciri yang unik: apabila (x -1) dilakukan dan operasi (&), nilai hasil selalu 0. Atribut ini boleh dinyatakan seperti berikut: <表示>

Untuk menghapuskan calon kuasa sifar sebagai 2, ia boleh diubah sedikit:

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

Penjelasan <解>

Semak kedudukan setiap bit perwakilan binari x dan (x -1) dengan kedudukan dan operasi (&). Jika kedua -duanya adalah 1, hasilnya adalah 1; Oleh itu, kuasa 2 adalah 0 dengan kedudukan (x -1) dan hasil pengiraan 0.

Kaedah ini menyediakan penyelesaian yang cekap dan langsung untuk menentukan sama ada nombor itu 2.

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

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