Jak sprawdzić, czy liczba jest potęgą 2

Dzisiaj potrzebowałem prostego algorytmu do sprawdzania, czy liczba jest potęgą 2.

Algorytm musi być:

1. Prosty
2. Prawidłowe dla dowolnej ulongwartości.

Wymyśliłem ten prosty algorytm:

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;
}

Ale potem pomyślałem, co powiesz na sprawdzenie, czy liczba jest dokładnie okrągła? Ale kiedy sprawdziłem 2 ^ 63 + 1, zwróciłem dokładnie 63 z powodu zaokrąglenia. Sprawdziłem więc, czy 2 do potęgi 63 jest równe pierwotnej liczbie - i jest tak, ponieważ obliczenia są wykonywane ws, a nie w dokładnych liczbach:log2 xMath.Logdouble

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

Ten wrócił truedo danej niewłaściwej wartości: 9223372036854775809.

Czy istnieje lepszy algorytm?

Istnieje prosty sposób na rozwiązanie tego problemu:

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

Uwaga: ta funkcja zgłosi się trueza 0, co nie jest potęgą 2. Jeśli chcesz to wykluczyć, oto jak:

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

Wyjaśnienie

Przede wszystkim bitowy operator binarny i operator z definicji MSDN:

Pliki binarne i operatory są predefiniowane dla typów integralnych i bool. Dla typów całkowitych oblicza logiczną wartość bitową AND swoich operandów. Dla argumentów bool i oblicza logiczne AND swoich argumentów; oznacza to, że wynik jest prawdziwy tylko wtedy, gdy oba operandy są prawdziwe.

Przyjrzyjmy się teraz, jak to wszystko wygląda:

Funkcja zwraca wartość logiczną (prawda / fałsz) i przyjmuje jeden przychodzący parametr typu bez znaku długi (w tym przypadku x). Załóżmy dla uproszczenia, że ​​ktoś przekroczył wartość 4 i wywołał funkcję w ten sposób:

bool b = IsPowerOfTwo(4)

Teraz zamieniamy każde wystąpienie x na 4:

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

Cóż, wiemy już, że 4! = 0 ewaluuje do prawdy, jak dotąd tak dobrze. Ale co z:

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

To oczywiście tłumaczy:

((4 & 3) == 0)

Ale czym dokładnie jest 4&3?

Binarna reprezentacja 4 wynosi 100, a binarna reprezentacja 3 to 011 (pamiętaj, że & przyjmuje binarną reprezentację tych liczb). Więc mamy:

100 = 4
011 = 3

Wyobraź sobie, że te wartości są zestawiane podobnie jak elementarne dodawanie. &Operator mówi, że jeśli obie wartości są równe 1 to wynikiem jest 1, w przeciwnym wypadku 0. Więc 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, i 0 & 1 = 0. Więc wykonujemy matematykę:

100
011
----
000

Wynik to po prostu 0. Wracamy więc do tego, co teraz przekłada się na naszą instrukcję return:

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

Co przekłada się teraz na:

return true && (0 == 0);

return true && true;

Wszyscy wiemy, że true && truejest to po prostu true, a to pokazuje, że w naszym przykładzie 4 jest potęgą 2.

Niektóre strony, które dokumentują i wyjaśniają to i inne kręcące się hacki, to:

• http://graphics.stanford.edu/~seander/bithacks.html
  ( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 )
• http://bits.stephan-brumme.com/
  ( http://bits.stephan-brumme.com/isPowerOfTwo.html )

I Grandaddy z nich, że książka „Delight hackerów” Henry Warren Jr :

• http://www.hackersdelight.org/

Jak wyjaśnia strona Seana Andersona , wyrażenie ((x & (x - 1)) == 0)niepoprawnie wskazuje, że 0 to potęga 2. Sugeruje użycie:

(!(x & (x - 1)) && x)

naprawić ten problem.

return (i & -i) == i

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

Ostatnio napisałem o tym artykuł na http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Obejmuje liczenie bitów, prawidłowe używanie logarytmów, klasyczne sprawdzanie „x &&! (X & (x - 1))” i inne.

Oto proste rozwiązanie C ++ :

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

Poniższy dodatek do zaakceptowanej odpowiedzi może być przydatny dla niektórych osób:

Potęga dwóch wyrażona w postaci binarnej zawsze będzie wyglądać jak 1, po której następuje n zer, gdzie n jest większe lub równe 0. Przykład:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

i tak dalej.

Kiedy odejmiemy 1od tego rodzaju liczb, stają się one 0, po których następuje n, i znowu n jest takie samo jak powyżej. Dawny:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

i tak dalej.

Przechodząc do sedna

Co się stanie, gdy wykonamy bitowe ORAZ liczby x, która jest potęgą 2 i x - 1?

Jeden z xzostaje wyrównany do zera x - 1i wszystkie zera xzostają wyrównane z zerami x - 1, powodując, że bitowe AND daje w wyniku 0. I w ten sposób otrzymaliśmy odpowiedź na jedną linię, o której mowa powyżej.

Dalsze zwiększenie piękna przyjętej odpowiedzi powyżej -

Mamy więc teraz do dyspozycji nieruchomość:

Kiedy odejmiemy 1 od dowolnej liczby, wówczas w reprezentacji binarnej skrajna prawa 1 stanie się 0, a wszystkie zera przed tą skrajną prawą 1 staną się teraz 1

Jednym z niesamowitych zastosowań tej właściwości jest ustalenie - ile jedynek jest obecnych w reprezentacji binarnej danej liczby? Krótki i słodki kod do zrobienia tego dla danej liczby całkowitej xto:

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

Innym aspektem liczb, który można udowodnić na podstawie powyższej koncepcji, jest „czy każda liczba dodatnia może być reprezentowana jako suma potęg 2?” .

Tak, każda liczba dodatnia może być reprezentowana jako suma potęg 2. Liczby binarne reprezentuje dowolna liczba. Np .: Weź numer 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

Po opublikowaniu pytania pomyślałem o następującym rozwiązaniu:

Musimy sprawdzić, czy dokładnie jedna z cyfr binarnych jest jedną. Więc po prostu przesuwamy liczbę w prawo o jedną cyfrę na raz i wracamy, truejeśli jest równa 1. Jeśli w dowolnym momencie otrzymamy nieparzystą liczbę ( (number & 1) == 1), wiemy, że wynik jest false. Okazało się to (przy użyciu testu porównawczego) nieco szybciej niż oryginalna metoda dla (dużych) wartości prawdziwych i znacznie szybciej dla wartości fałszywych lub małych.

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

Oczywiście rozwiązanie Grega jest znacznie lepsze.

    bool IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

A oto ogólny algorytm sprawdzania, czy liczba jest potęgą innej liczby.

    bool IsPowerOf(int n,int b)
    {
        if (n > 1)
        {
            while (n % b == 0)
            {
                n /= b;
            }
        }
        return n == 1;
    }

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

Sprawdź, czy podana liczba jest potęgą 2.

#include <math.h>

int main(void)
{
    int n,logval,powval;
    printf("Enter a number to find whether it is s power of 2\n");
    scanf("%d",&n);
    logval=log(n)/log(2);
    powval=pow(2,logval);

    if(powval==n)
        printf("The number is a power of 2");
    else
        printf("The number is not a power of 2");

    getch();
    return 0;
}

bool isPowerOfTwo(int x_)
{
  register int bitpos, bitpos2;
  asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
  asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
  return bitpos > 0 && bitpos == bitpos2;
}

int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

To jest naprawdę szybkie. Sprawdzanie wszystkich liczb całkowitych 2 ^ 32 zajmuje około 6 minut i 43 sekund.

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

Jeśli xjest potęgą dwóch, jego samotny 1 bit jest na swoim miejscu n. Oznacza to, że x – 1ma pozycję 0 n. Aby zobaczyć dlaczego, przypomnij sobie, jak działa odejmowanie binarne. Odejmując 1 od x, pożyczka rozprzestrzenia się aż do pozycji n; bit nstaje się 0, a wszystkie niższe bity stają się 1. Teraz, ponieważ xnie ma 1 wspólnego bitu x – 1, x & (x – 1)ma wartość 0 i !(x & (x – 1))jest prawdziwe.

Liczba jest potęgą 2, jeśli zawiera tylko 1 ustawiony bit. Możemy użyć tej właściwości i funkcji ogólnejcountSetBits aby sprawdzić, czy liczba jest potęgą 2, czy nie.

To jest program w C ++:

int countSetBits(int n)
{
        int c = 0;
        while(n)
        {
                c += 1;
                n  = n & (n-1);
        }
        return c;
}

bool isPowerOfTwo(int n)
{        
        return (countSetBits(n)==1);
}
int main()
{
    int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
    for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
        printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
    return 0;
}

Nie musimy jawnie sprawdzać, czy 0 jest potęgą 2, ponieważ zwraca również False dla 0.

WYNIK

Num:0   Set Bits:0   is power of two: 0
Num:1   Set Bits:1   is power of two: 1
Num:2   Set Bits:1   is power of two: 1
Num:3   Set Bits:2   is power of two: 0
Num:4   Set Bits:1   is power of two: 1
Num:5   Set Bits:2   is power of two: 0
Num:15  Set Bits:4   is power of two: 0
Num:16  Set Bits:1   is power of two: 1
Num:22  Set Bits:3   is power of two: 0
Num:32  Set Bits:1   is power of two: 1
Num:38  Set Bits:3   is power of two: 0
Num:64  Set Bits:1   is power of two: 1
Num:70  Set Bits:3   is power of two: 0

Oto inna metoda, którą opracowałem, w tym przypadku używając |zamiast &:

bool is_power_of_2(ulong x) {
    if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
    return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

dla dowolnej potęgi 2, obowiązuje również:

n & (- n) == n

UWAGA: kończy się niepowodzeniem dla n = 0, więc należy to sprawdzić.
Powód, dla którego to działa:
-n jest uzupełnieniem 2s n. -n będzie miał odwrócony bit po lewej stronie najbardziej ustawionego bitu n w porównaniu do n. Dla mocy 2 jest tylko jeden ustawiony bit.

Przykład

0000 0001    Yes
0001 0001    No

Algorytm

1. Za pomocą maski bitowej podziel NUMzmienną na binarną

2. IF R > 0 AND L > 0: Return FALSE

3. W przeciwnym razie NUMstaje się niezerowym

4. IF NUM = 1: Return TRUE

5. W przeciwnym razie przejdź do kroku 1

Złożoność

Czas ~ O(log(d))gdzie djest liczbą cyfr binarnych

Poprawa odpowiedzi @ user134548, bez arytmetyki bitów:

public static bool IsPowerOfTwo(ulong n)
{
    if (n % 2 != 0) return false;  // is odd (can't be power of 2)

    double exp = Math.Log(n, 2);
    if (exp != Math.Floor(exp)) return false;  // if exp is not integer, n can't be power
    return Math.Pow(2, exp) == n;
}

Działa to dobrze dla:

IsPowerOfTwo(9223372036854775809)

Mark gravell zasugerował to, jeśli masz .NET Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

Pojedyncza instrukcja, szybsza niż, (x != 0) && ((x & (x - 1)) == 0)ale mniej przenośna.

W C przetestowałem i && !(i & (i - 1)sztuczkę i porównałem ją __builtin_popcount(i), używając gcc w Linuksie, z flagą -mpopcnt, aby mieć pewność, że użyję instrukcji POPCNT CPU. Mój program testowy policzył liczbę całkowitą od 0 do 2 ^ 31, która była potęgą dwóch.

Na początku myślałem, że i && !(i & (i - 1)to 10% szybciej, mimo że zweryfikowałem, że POPCNT został użyty przy demontażu, w którym go użyłem __builtin_popcount.

Uświadomiłem sobie jednak, że załączyłem instrukcję if, a przewidywanie gałęzi prawdopodobnie lepiej działało w wersji z nieco zmienną wersją. Usunąłem if i POPCNT skończyło się szybciej, zgodnie z oczekiwaniami.

Wyniki:

Procesor Intel (R) Core (TM) i7-4771 maks. 3,90 GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

16-rdzeniowy procesor AMD Ryzen Threadripper 2950X maks. 3,50 GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

Zauważ, że tutaj procesor Intel wydaje się nieco wolniejszy niż AMD z nieco kręcącym się, ale ma znacznie szybszy POPCNT; AMD POPCNT nie zapewnia tak dużej poprawy.

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

Uruchom testy:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

Widzę, że wiele odpowiedzi sugeruje zwrócenie n &&! (N & (n - 1)), ale według mojego doświadczenia, jeśli wartości wejściowe są ujemne, zwraca wartości fałszywe. Podzielę się tutaj innym prostym podejściem, ponieważ wiemy, że potęga dwóch liczb ma tylko jeden ustawiony bit, więc po prostu policzymy liczbę ustawionych bitów, zajmie to czas O (log N).

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

Sprawdź ten artykuł, aby policzyć nie. ustawionych bitów

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

Ten program w Javie zwraca „prawda”, jeśli liczba jest potęgą 2, i zwraca „fałsz”, jeśli nie jest potęgą 2

// To check if the given number is power of 2

import java.util.Scanner;

public class PowerOfTwo {
    int n;
    void solve() {
        while(true) {
//          To eleminate the odd numbers
            if((n%2)!= 0){
                System.out.println("false");
                break;
            }
//  Tracing the number back till 2
            n = n/2;
//  2/2 gives one so condition should be 1
            if(n == 1) {
                System.out.println("true");
                break;
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        PowerOfTwo obj = new PowerOfTwo();
        obj.n = in.nextInt();
        obj.solve();
    }

}

OUTPUT : 
34
false

16
true