Power of Two

Q: Jak sprawdzić, czy liczba jest potęgą dwójki?

Zwróć true, gdy n > 0 i n & (n-1) jest równe 0. Potęga dwójki ma dokładnie jeden bit 1, a odjęcie 1 zeruje go i ustawia tylko bity znajdujące się poniżej niego, więc wynik AND wynosi 0. Bez operacji bitowych dziel n przez 2, dopóki jest parzyste, i sprawdź, czy otrzymasz 1.

Q: Jaka jest złożoność czasowa algorytmu sprawdzającego, czy liczba jest potęgą dwójki?

Sprawdzenie n & (n-1) działa w czasie i zajmuje pamięć rzędu O(1) : jedno porównanie, jedno odejmowanie i jedna operacja AND. Pętla dzieląca przez 2 działa w czasie rzędu O(log n) , maksymalnie 31 kroków dla 32-bitowej liczby całkowitej.

ŁatweOperacje na bitach

+10

Otrzymujesz liczbę całkowitą n. Zwróć true, jeśli n jest potęgą dwójki, czyli n = 2^k dla pewnej liczby całkowitej k ≥ 0, a w przeciwnym razie zwróć false. Zatem 1, 2, 4 i 8 się liczą, a 0, 6 i każda liczba ujemna — nie.

Funkcja

isPowerOfTwo(n: integer) → boolean

ninteger: liczba całkowita do sprawdzenia, która może być równa zero lub ujemna
Zwracaboolean: true, jeśli n jest równe 2^k dla pewnego k ≥ 0, w przeciwnym razie false

Ograniczenia

-2³¹ ≤ n ≤ 2³¹-1

Przykłady

Wejście: n = 16
Wyjście: true
Wyjaśnienie: 16 = 2 × 2 × 2 × 2 = 2^4. W systemie binarnym to 10000, pojedynczy bit 1.

Wejście: n = 24
Wyjście: false
Wyjaśnienie: 24 = 8 × 3. Dzielenie przez 2 daje 12, 6, a następnie 3, które jest nieparzyste, ale nie równa się 1. W systemie binarnym 24 to 11000, czyli dwa bity 1.

Wejście: n = 1
Wyjście: true
Wyjaśnienie: 1 = 2^0, więc jest potęgą dwójki. Jego postać binarna 1 ma dokładnie jeden bit o wartości 1.

Pytanie dodatkowe

Czy za pomocą tych samych sztuczek bitowych potrafisz sprawdzić, czy n jest potęgą czwórki, bez użycia pętli?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Potęga liczby 2 ma w systemie binarnym stały kształt: jeden bit 1, po którym następują zera, jak w 10000 dla 16. Możesz potwierdzić ten kształt, dzieląc n przez 2, aż stanie się nieparzyste, co zajmuje do 31 kroków. Możesz też potwierdzić go w jednym kroku za pomocą n & (n-1), które zeruje najniższy bit 1 i daje 0 tylko wtedy, gdy ten bit był jedynym. W obu wersjach najpierw sprawdza się znak, ponieważ zero i liczby ujemne powodują błędne działanie oczywistego kodu.

Podziel przez 2, gdy liczba jest parzysta

Intuicja

Jeśli n = 2^k, możesz podzielić je przez 2 dokładnie k razy i dojść do 1, a każda wartość po drodze jest parzysta. Jeśli n ma nieparzysty czynnik większy niż 1, dzielenie przez 2 zatrzyma się na nieparzystej liczbie, która nie jest równa 1. Dla 16: 16, 8, 4, 2, 1, więc odpowiedź to true. Dla 24: 24, 12, 6, 3, a 3 jest nieparzyste, ale nie jest równe 1, więc odpowiedź to false.

Zwróć false dla n ≤ 0 przed pętlą. Żadna potęga dwójki nie jest zerem ani liczbą ujemną, a pętla nigdy nie zakończy się na 0, ponieważ 0 jest parzyste, a połowa z 0 to nadal 0.

Każdy krok zmniejsza n o połowę, więc przetworzenie 32-bitowej wartości wejściowej wymaga najwyżej 31 kroków: czas O(log n) i pamięć O(1).

Algorytm

Jeśli n ≤ 0, zwróć false.
Gdy n jest parzyste, dziel je przez 2.
Zwróć informację, czy n wynosi teraz 1.

def isPowerOfTwo(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Wyczyść najmłodszy ustawiony bit za pomocą n & (n-1)

Intuicja

Zapisz potęgę dwójki w systemie binarnym, a otrzymasz pojedynczą jedynkę, po której następują zera: 16 to 10000. Odjęcie 1 zamienia tę jedynkę na 0, a każde zero poniżej niej na 1: 15 to 01111. Te dwie liczby nie mają wspólnego bitu 1, więc 16 & 15 wynosi 0.

Każda inna liczba dodatnia ma co najmniej dwa bity 1. Odjęcie 1 zmienia tylko najniższy bit 1 i zera poniżej niego, więc każdy wyższy bit 1 występuje w obu liczbach, a wynik operacji AND nie jest równy 0. Dla 24, czyli 11000, otrzymujemy 23 = 10111, a 24 & 23 to 10000, czyli 16.

Najpierw sprawdź n > 0. 0 & -1 wynosi 0, a w arytmetyce 32-bitowej -2^31 to pojedynczy bit 1, po którym następuje 31 zer, więc samo AND uznałoby obie te wartości za potęgi dwójki. Cały test obejmuje jedno porównanie, jedno odejmowanie i jedną operację AND: czas i pamięć O(1). Lua 5.1 nie ma operatora AND, więc kod w Lua składa wynik AND bit po bicie, wykonując do 31 kroków dla 32-bitowego n; test jest taki sam.

Algorytm

Jeśli n ≤ 0, zwróć false.
Oblicz n & (n-1), czyli n z wyzerowanym najniższym bitem o wartości 1.
Zwróć informację, czy wynik jest równy 0.

def isPowerOfTwo(n):
    # One set bit: n - 1 flips it and every bit below, so the AND is 0.
    return n > 0 and n & (n - 1) == 0

Pułapki i przypadki brzegowe

Test bitowy to tylko jedna linia, a większość błędów dotyczy danych wejściowych, dla których nie został zaprojektowany.

Pominięcie sprawdzenia znaku. 0 & (0-1) daje 0, więc 0 przechodzi test AND. W przypadku liczb całkowitych 32-bitowych -2^31 również przechodzi, ponieważ jego postać binarna zawiera tylko jeden bit 1. Oba przypadki muszą zwracać false.
Uruchomienie pętli dzielenia przez 2 dla 0. Zero jest parzyste, a podzielenie go przez 2 ponownie daje 0, więc pętla nigdy się nie kończy.
Pominięcie nawiasów. == ma wyższy priorytet niż &, więc w C, C++ i JavaScript wyrażenie n & n - 1 == 0 jest interpretowane jako n & ((n - 1) == 0) i daje nieprawidłowy wynik bez żadnego błędu; Java i C# odrzucają je jako błąd typu. Zapisz (n & (n - 1)) == 0.
Używanie logarytmów. W arytmetyce podwójnej precyzji log(536870912) / log(2) daje 29.000000000000004 zamiast 29, więc sprawdzenie, czy wynik jest liczbą całkowitą, uznaje 2^29 za false.

Najczęstsze pytania3

Jak sprawdzić, czy liczba jest potęgą dwójki?

Zwróć true, gdy n > 0 i n & (n-1) jest równe 0. Potęga dwójki ma dokładnie jeden bit 1, a odjęcie 1 zeruje go i ustawia tylko bity znajdujące się poniżej niego, więc wynik AND wynosi 0. Bez operacji bitowych dziel n przez 2, dopóki jest parzyste, i sprawdź, czy otrzymasz 1.

Dlaczego n & (n-1) zeruje najmłodszy ustawiony bit?

Odjęcie 1 powoduje pożyczenie od najmłodszego bitu o wartości 1: ten bit zmienia się w 0, a każdy 0 poniżej niego zmienia się w 1, podczas gdy wyższe bity pozostają takie same. Operacja AND z wartością początkową zachowuje tylko bity ustawione w obu wartościach, czyli dokładnie wyższe bity. Dla potęgi dwójki nie ma wyższych bitów, więc wynikiem jest 0.

Jaka jest złożoność czasowa algorytmu sprawdzającego, czy liczba jest potęgą dwójki?

Sprawdzenie n & (n-1) działa w czasie i zajmuje pamięć rzędu O(1): jedno porównanie, jedno odejmowanie i jedna operacja AND. Pętla dzieląca przez 2 działa w czasie rzędu O(log n), maksymalnie 31 kroków dla 32-bitowej liczby całkowitej.

def isPowerOfTwo(n):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

n = 16

Oczekiwany wynik

true