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

584

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?

konfigurator
źródło
1
Myślę, że rozwiązanie (x & (x - 1))może zwrócić wyniki fałszywie dodatnie, gdy Xjest sumą potęg dwóch, np 8 + 16.
Joe Brown,
32
Wszystkie liczby można zapisać jako sumę potęg dwóch, dlatego możemy reprezentować dowolną liczbę dwójkową. Ponadto twój przykład nie zwraca fałszywie dodatniego wyniku, ponieważ 11000 i 10111 = 10000! = 0.
vlsd 24.11.11
1
@JoeBrown Nie ma żadnych fałszywych alarmów. W rzeczywistości wyrażenie zwraca większą z dowolnej sumy dwóch potęg dwóch.
Samy Bencherif,

Odpowiedzi:

1219

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.

Greg Hewgill
źródło
56
@Kripp: Liczba będzie miała postać binarną 1000 ... 000. Kiedy -1, będzie miał postać 0111 ... 111. Zatem dwójkowa liczba dwójkowa i wynik to 000000. Nie stanie się tak w przypadku braku mocy dwójki, ponieważ na przykład 1010100 zmieni się w 1010011, co spowoduje (kontynuacja ...)
konfigurator
47
... Wynik 1010000 po binarnym i. Jedynym fałszywie dodatnim byłoby 0, dlatego użyłbym: return (x! = 0) && ((x & (x - 1)) == 0);
konfigurator
6
Kripp, rozważ (2: 1, 10: 1) (4: 3, 100: 11) (8: 7, 1000: 111) (16:15, 10000: 1111) Widzisz wzór?
Thomas L Holaday
13
@ShuggyCoUk: uzupełnieniem do dwóch jest sposób reprezentowania liczb ujemnych. Ponieważ jest to liczba całkowita bez znaku, reprezentacja liczb ujemnych nie ma znaczenia. Ta technika opiera się tylko na binarnej reprezentacji nieujemnych liczb całkowitych.
Greg Hewgill
4
@ SoapBox - co jest bardziej powszechne? Zera lub niezerowe liczby, które nie są potęgami dwóch? To pytanie, na które nie można odpowiedzieć bez większego kontekstu. I tak naprawdę to naprawdę nie ma znaczenia.
konfigurator
97

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

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

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.

Michael Burr
źródło
4
0 to potęga 2 ... 2 ^ -inf = 0.;););)
Michael Bray
4
Ponieważ jest to wątek oznaczony jako C # , warto zauważyć, że ostatnie wyrażenie (Seana Andersona) jest nielegalne w języku C #, ponieważ !może być stosowane tylko do typów boolowskich, a &&także wymaga, aby oba operandy były logiczne - (z wyjątkiem operatorów zdefiniowanych przez użytkownika umożliwiają inne rzeczy, ale nie dotyczy to ulong.)
Jeppe Stig Nielsen
40

return (i & -i) == i

Andreas Petersson
źródło
2
jakaś wskazówka, dlaczego to działa lub nie działa? sprawdziłem jego poprawność tylko w java, gdzie są tylko podpisane ints / longs. jeśli jest to poprawne, byłaby to najlepsza odpowiedź. szybciej + mniej
Andreas Petersson
7
Wykorzystuje jedną z właściwości notacji uzupełnienia do dwóch: do obliczenia wartości ujemnej liczby wykonujesz negację bitową i dodajesz 1 do wyniku. iUstawiony zostanie również najmniej znaczący bit, który zostanie ustawiony -i. Bity poniżej tego będą wynosić 0 (w obu wartościach), a bity powyżej będą odwrócone względem siebie. Wartość i & -ibędzie zatem najmniej znaczącym ustawionym bitem w i(który jest potęgą dwóch). Jeśli ima taką samą wartość, to był to jedyny ustawiony bit. Błąd kończy się, gdy iwynosi 0 z tego samego powodu i & (i - 1) == 0.
Michael Carman,
6
Jeśli ijest to typ bez znaku, dopełnianie dwójki nie ma z tym nic wspólnego. Po prostu wykorzystujesz właściwości modułowej arytmetyki i bitowej i.
R .. GitHub ZATRZYMAJ LÓD
2
To nie działa, jeśli i==0(zwraca, (0&0==0)co jest true). Powinno byćreturn i && ( (i&-i)==i )
bobobobo
22
bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}
Matt Howells
źródło
3
To rozwiązanie jest lepsze, ponieważ może również radzić sobie z liczbą ujemną, jeśli ujemna byłaby w stanie przejść. (Jeśli długa zamiast długa)
Steven
Dlaczego przecinek dziesiętny przechodzi jako potęga dwóch w tym przypadku?
Chris Frisina
17

Oto proste rozwiązanie C ++ :

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}
deft_code
źródło
8
na gcc to kompiluje się do jednego wbudowanego gcc o nazwie __builtin_popcount. Niestety, jedna rodzina procesorów nie ma jeszcze jednej instrukcji asemblera (x86), więc jest to najszybsza metoda liczenia bitów. W każdej innej architekturze jest to pojedyncza instrukcja montażu.
deft_code,
3
@deft_code nowsza obsługa mikroarchitektur x86popcnt
phuclv
13

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
wyświetlana nazwa
źródło
@Michi: Czy twierdziłem, że 0 to liczba dodatnia? Czy potęga 2?
displayName
Tak, podając 0 jako przykład i czyniąc matematykę wewnątrz tej reprezentacji binarnej. To powoduje zamieszanie.
Michi
1
Jeśli dodanie dwóch liczb dezorientuje cię do przekonania, że ​​muszą być pozytywne, nie mogę nic na to poradzić. Co więcej, zera pokazano w reprezentacji, aby sugerować, że ta moc 2 jest pomijana w tej liczbie. Każdy, kto zna podstawową matematykę, wie, że dodanie 0 oznacza brak dodawania czegokolwiek.
displayName
10

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.

konfigurator
źródło
10
    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;
    }
Raz Megrelidze
źródło
6
bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;
Abelenky
źródło
1
Czy to c#jest Wydaje mi się, że to jest c++tak, jak xjest zwracane jako bool.
Mariano Desanze,
1
Napisałem to jako C ++. Aby to zrobić C # jest banalny: bool isPow2 = ((x & ~ (x-1)) == x)? x! = 0: fałsz;
abelenky
4

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;
}
udhaya
źródło
Lub w języku C #: return x == Math.Pow (2, Math.Log (x, 2));
konfigurator
4
Złamany. Cierpi z powodu głównych problemów z zaokrąglaniem zmiennoprzecinkowym. Użyj frexpraczej nieprzyjemnych logrzeczy, jeśli chcesz użyć zmiennoprzecinkowego.
R .. GitHub ZATRZYMAJ POMOC ICE
4
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;
}
król błędów
źródło
4
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.

sudeepdino008
źródło
4
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.

Prakash Jat
źródło
3

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
jerrymouse
źródło
zwracanie c jako „int”, gdy funkcja ma typ zwracany „ulong”? Używasz whilezamiast zamiast if? Osobiście nie widzę powodu, ale wydaje się, że działa. EDYCJA: - nie ... zwróci 1 za coś większego niż 0!?
James Khoury
@JamesKhoury Pisałem program w C ++, więc przez pomyłkę zwróciłem int. Było to jednak małe literówki i nie zasługiwało na opinię. Ale nie rozumiem uzasadnienia pozostałej części twojego komentarza: „użyj while zamiast if” i „zwróci 1 dla wartości większej niż 0”. Dodałem główny kod, aby sprawdzić wyjście. AFAIK to oczekiwana wydajność. Popraw mnie, jeśli się mylę.
jerrymouse
3

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));
}
Chethan
źródło
Potrzebujesz (x > 0)trochę tutaj?
konfigurator
@ konfigurator, tak, w przeciwnym razie is_power_of_2 (0) zwróciłoby wartość true
Chethan
3

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.

FReeze FRancis
źródło
2

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

Khaled.K
źródło
1

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)
rodan
źródło
operacje zmiennoprzecinkowe są znacznie wolniejsze niż proste wyrażenie bitowe
phuclv
1

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.

jbat100
źródło
jesteś pewien, że jest szybszy niż (x != 0) && ((x & (x - 1)) == 0)? Wątpię w to, szczególnie. na starszych systemach, w których popcnt nie jest dostępny
phuclv
To nie jest szybsze. Właśnie przetestowałem to na nowoczesnym procesorze Intel i zweryfikowałem POPCNT w użyciu podczas dezasemblacji (przyznane, w kodzie C, a nie .NET). POPCNT jest ogólnie szybszy do liczenia bitów, ale w przypadku pojedynczego bitu sztuczka kręcenia bitów jest jeszcze szybsza o 10%.
eraoul
Ups, cofam to. Testowałem w pętli, jeśli myślę, że przewidywanie gałęzi to „oszustwo”. POPCNT jest rzeczywiście pojedynczą instrukcją, która działa w jednym cyklu zegara i jest szybsza, jeśli jest dostępna.
eraoul
0

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
eraoul
źródło
0

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

Anil Gupta
źródło
-1
private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}
użytkownik134548
źródło
Spróbuj tego dla numeru 9223372036854775809. Czy to działa? Nie sądzę, ze względu na błędy zaokrąglania.
konfigurator
1
@configurator 922337203685477580_9_ dla mnie nie wygląda na potęgę 2;)
Kirschstein
1
@Kirschstein: ta liczba dała mu fałszywie dodatni wynik.
Erich Mirabal
7
Kirschstein: Dla mnie też to nie wygląda. Ta funkcja wygląda jednak jak jedna ...
konfigurator
-2

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
K_holla
źródło
1
to pytanie jest oznaczone jako C #, a twoje rozwiązanie jest również bardzo wolne w porównaniu do poprzednich rozwiązań [
phuclv