Power of Two
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
- 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
-231 ≤ n ≤ 231-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
1ma dokładnie jeden bit o wartości 1.
+17 ukrytych testów przy wysłaniu
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.
Zapisz kilka potęg liczby dwa w systemie binarnym:
1,10,100,1000. Co łączy je wszystkie, a czego nie ma 6 (110)?Potęga liczby 2 ma dokładnie jeden bit o wartości 1. Porównaj
nzn-1w systemie binarnym: odjęcie 1 zmienia najmłodszy bit o wartości 1 na 0, a każdy bit o wartości 0 poniżej niego na 1.Zatem
njest potęgą liczby dwa dokładnie wtedy, gdy jest dodatnie i wykonanie operacji AND na nim in-1daje 0. Najpierw sprawdź znak, a dopiero potem bity, ponieważ 0 i liczby ujemne nigdy nie są potęgami liczby dwa.
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
njest parzyste, dziel je przez 2. - Zwróć informację, czy
nwynosi teraz 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Wyczyść 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), czylinz 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^31ró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żenien & n - 1 == 0jest interpretowane jakon & ((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ą, uznaje2^29za false.
Najczęstsze pytania4
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.
Czy 1 jest potęgą liczby 2? A 0?
1 jest potęgą dwójki, ponieważ 2^0 = 1, a w jego zapisie binarnym jest jeden bit o wartości 1. 0 nią nie jest: żaden całkowity wykładnik nie daje 0, a liczba ta nie ma ani jednego bitu o wartości 1. Liczby ujemne również nigdy nie są potęgami dwójki.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def isPowerOfTwo(n):
# Wpisz tutaj kodPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
n = 16
Oczekiwane
true