Potęga liczby 2
Lekcja 9 z 17 w kursie Operacje bitowe w Coddy.
Jeśli masz już za sobą wystarczająco dużo zabawy z liczbami binarnymi, to zapewne zauważyłeś, że każda potęga liczby 2 zawiera tylko 1 ustawiony bit (ustawiony bit oznacza „1”). Na przykład: (2)10 = (10)2 , (4)10 = (100)2 , (8)10 = (1000)2 i tak dalej.
W tej lekcji omówimy problem:
Ustal, czy dana liczba jest potęgą liczby 2, używając operacji bitowych.
Dobrze! Jak więc powyższa obserwacja może nam pomóc? Sprawdźmy.
- Załóżmy, że dana jest nam liczba (8)10 i wiemy, że jest potęgą liczby 2.
- Odejmując od niej 1, otrzymujemy (7)10, co jest równoważne (0111)2.
- Jeśli wykonamy operację AND ( & ) na liczbach 7 i 8, otrzymamy 0.
- Ciekawe, prawda? Sprawdźmy inną liczbę, która również jest potęgą liczby 2. Weźmy (32)10, co jest równoważne (100000)2, i odejmijmy od niej 1, czyli (31)10 = (011111)2. Ponownie otrzymujemy 0!
- Uogólniając, czy możemy stwierdzić, że dla liczby, którą nazwiemy x, będącej potęgą liczby 2, ( x & (x-1) ) zawsze będzie równe „0”?
Korzystając z tej obserwacji, możemy łatwo rozwiązać to zadanie bez używania biblioteki matematycznej ani jej funkcji potęgowania. Nie musimy też używać żadnej pętli — rozwiązaliśmy je w czasie O(1)! Czy to nie świetne? Właśnie tak operacje bitowe mogą pomóc nam znacznie zoptymalizować nasze programy, a także sprawić, że kod będzie mniej skomplikowany.
Wyzwanie
ŁatwyMając daną liczbę, ustal za pomocą operacji bitowych, czy jest parzysta.
Spróbuj swoich sił
#include <iostream>
using namespace std;
bool IsPowerOf2(int num) {
// Wpisz kod tutaj
}Wszystkie lekcje w sekcji Operacje bitowe
2Algorytmy bitowe
Potęga liczby 2Liczba występująca nieparzystą liczbę razyLiczba ustawionych bitówRotacja bitów liczby IRotacja bitów liczby IIPoćwicz samodzielnie: Kompilator C++ online