Bugün eğer bir sayı 2 Bir güç olup olmadığını kontrol için basit bir algoritmaya ihtiyacım vardı.

Algoritma olması gerekir:

1. Basit
2. ulong herhangi bir değer için doğru.

Bu basit bir algoritma ile geldi:

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

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

Ama sonra düşündüm ki, nasıl kontrol hakkında log2 x tam olarak yuvarlak bir sayı ise? Ama, *2^63 1* 16 tam 63 yüzünden yuvarlama için iade ettim. Hesaplama tam sayılar doubles ve yapılır çünkü 2 ise 63 orijinal sayısına eşit olduğu ve bu gücü kontrol ettim, böylece:

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

Bu verilen yanlış bir değer için true iade: 9223372036854775809.

Daha iyi bir algoritma var mı?

Bu sorun için basit bir numara var:

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

Eksiksiz, sıfır iki bir güç değildir. Eğer hesaba kenar davayı almak istiyorsanız, işte yapmanız gerekenler:

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

Açıklama

İlk ve MSDN tanımı: ikili bit tabanlı & operatörü en önemlisi

İkili & operatörler, integral çeşitleri ve bool için önceden tanımlanmıştır. İçin integral tipleri, & hesaplar mantıksal bit VE işlenen. Bool işlenen, & hesaplar mantıksal VE işlenen; sonuç ve eğer her iki işlenen doğruysa. eğer doğruysa.

Bakalım bu işin sonunu nasıl bir göz atın:

İşlev döndürür (true / false) boolean ve türü işaretsiz uzun gelen parametre kabul eder (x, bu durumda). Kolaylık olması için bizden birinin değeri 4 geçti varsayalım: bu fonksiyonu denir

bool b = IsPowerOfTwo(4)

Şimdi 4 x her geçtiği gibi değiştiriyoruz:

return (4 != 0) && ((4 & (4-1)) == 0);

4 ! Bu zaten bildiğimiz bir şey= 0 true, şimdiye kadar çok iyi değerlendirmeler. Ama ne için:

((4 & (4-1)) == 0)

Bu tabii ki bu bizimle iletişime geçiniz

((4 & 3) == 0)

Ama tam olarak 4&3 nedir?

4 ikili gösterimini 100 ve 3 temsili 011 (hatırla & sürer bu sayıların ikili gösterimi. ikili Var:

100 = 4
011 = 3

Bu değerler çok temel olarak yığılmış hayal edin. & operatörü ise her iki değer sonuç 1, aksi takdirde 1 eşittir 0 olduğunu söylüyor. Yani, *, *321 & 1 = 11 & 0 = 0, 0 & 1 = 0. Matematik yapalım:

100
011
----
000

Sonuç sadece 0. Biz geri gitmek ve geri dönmek için, beyan şimdi ne çevirir bak:

return (4 != 0) && ((4 & 3) == 0);

Hangi çevirir şimdi için:

return true && (0 == 0);

return true && true;

Biz true && true sadece true ve 4 örneğin 2 Bir güç olduğunu gösterir.