Liczba ustawionych bitów
Lekcja 11 z 17 w kursie Operacje bitowe w Coddy.
Na początek: czym są ustawione bity?
Cyfra „1” w liczbach binarnych jest w terminologii komputerowej nazywana ustawionym bitem.
W tej lekcji chcemy obliczyć:
Liczbę ustawionych bitów w postaci binarnej podanej liczby.
Załóżmy na przykład, że mamy liczbę (20)10 w postaci binarnej (10100)2. W liczbie (20)10 są 2 ustawione bity.
Spróbuj wymyślić podejście. Prawdopodobnie pomyślisz o przekształceniu liczby na postać binarną i policzeniu jedynek. W porządku, ale co z dużymi liczbami? Nie będziesz w stanie przechować ich w typie całkowitoliczbowym. Jak zatem ustalimy liczbę ustawionych bitów w dużych liczbach? Odpowiedzią jest oczywiście manipulowanie bitami!
- Najpierw bierzemy zmienną pozycji, nazwijmy ją pos, aby wiedzieć, który bit znajduje się na danej pozycji w liczbie binarnej.
- Następnie przesuwamy bit pos razy w lewo w liczbie 1.
- Potem po prostu wykonujemy operację AND na podanej liczbie.
Jak to działa? Przyjrzyjmy się liczbie (20)10:
- Dla pierwszej pozycji pos=0.
20 & 1<<pos, 1<<pos=1, a wykonanie operacji AND na (10100)2 i (00001)2 daje nam zero. - Dla drugiej pozycji pos=1.
20 & 1<<pos, 1<<pos=(10)2, a wykonanie operacji AND na (10100)2 i (00010)2 daje nam zero. - Dla trzeciej pozycji pos=2.
20 & 1<<pos, 1<<pos=(100)2, a wykonanie operacji AND na (10100)2 i (00100)2 daje nam jeden, czyli nasz pierwszy ustawiony bit. - Dla czwartej pozycji pos=2.
20 & 1<<pos, 1<<pos=(1000)2, a wykonanie operacji AND na (10100)2 i (01000)2 daje nam zero. - Dla trzeciej pozycji pos=2.
20 & 1<<pos, 1<<pos=(10000)2, a wykonanie operacji AND na (10100)2 i (10000)2 daje nam jeden, czyli drugi ustawiony bit.
Aby policzyć ustawione bity, możemy użyć zmiennej licznika. Mam jednak nadzieję, że ten przykład wyjaśnił ci działanie algorytmu.
W ten sposób możemy łatwo obliczyć liczbę ustawionych bitów w postaci binarnej liczby, nie martwiąc się o przekroczenie zakresu typu int w C++.
Wyzwanie
ŚredniUzupełnij funkcję SetBits, aby zwracała liczbę ustawionych bitów w podanej liczbie, używając powyższego podejścia.
Spróbuj swoich sił
#include <cmath>
int SetBits(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