[C++] Zliczanie jedynek w liczbie binarnej

pytanie zadane 8 września 2019 w C i C++ przez mm Użytkownik (890 p.)

Cześć!

Chciałabym się dowiedzieć w jaki sposób można zliczyć ilość jedynek występujących w liczbie binarnej?

Dzięki za odpowiedź

3 odpowiedzi

odpowiedź 8 września 2019 przez adrian17 Ekspert (344,860 p.)

odpowiedź 8 września 2019 przez mokrowski Mędrzec (155,460 p.)

Metoda naiwna, to zliczanie zapalonego bitu na pozycji 0 (zero) i przesuwanie wartości w prawo o jeden bit aż do momentu gdy wynikiem przesunięcia nie będzie zero:

#include <iostream>

unsigned short count_bits(unsigned value) {
    unsigned short counter = 0;
    while(value != 0) {
        if((value & 0x01) == 1) {
            ++counter;
        }
        value >>= 1;
    }
    return counter;
}

int main() {
    unsigned value = 127;
    std::cout << "value = " << value << ", counting bits = " << count_bits(value) << '\n';
}

Bardziej skomplikowane (ale i wydajniejsze) metody, wymagają zastosowania operacji arytmetycznych i logicznych. Tylko pytanie czy aż tak bardzo tego potrzebujesz?

#include <iostream>
#include <cstdint>

unsigned short count_bits(uint32_t value) {
     value = value - ((value >> 1) & 0x55555555);
     value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
     return (((value + (value >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    unsigned value = 127;
    std::cout << "value = " << value << ", counting bits = " << count_bits(value) << '\n';
}

To ostatnie bazuje na algorytmie: https://en.wikipedia.org/wiki/Hamming_weight

komentarz 8 września 2019 przez tkz Nałogowiec (42,000 p.)

Przy jakich liczbach jest zauważalna różnica?

komentarz 8 września 2019 przez mokrowski Mędrzec (155,460 p.)

Wersja naiwna ze zliczaniem bitów:

https://godbolt.org/z/WUydVh

Wersja z Hamming'iem:

https://godbolt.org/z/EqHv-7

(zwróć uwagę na brak rozgałęzień)

Dodaj np. jeszcze optymalizację -Os (minus Ooo Ess) a będziesz zdziwiony wynikami.

Tu masz to o czym szkoda mówić...:

https://godbolt.org/z/gwwY02

A odpowiadając, już przy 16 bitach na (w zasadzie) wszystkich platformach sprzętowych widać różnicę.

komentarz 8 września 2019 przez tkz Nałogowiec (42,000 p.)

Stringa nawet nie brałem pod uwagę. Bardziej chodziło mi o czas. Robiłem sobie testy i w sumie wyniki takie same, kompletnie nie patrząc na assemblera. Oczywiście porównywałem tylko Twoje dwie funkcję. Wyniki mam na myśli czas wykonywania.

odpowiedź 8 września 2019 przez manjaro Nałogowiec (37,390 p.)

Zamienić na stringa i znak po znaku sprawdzać 1 czy 0

komentarz 8 września 2019 przez mokrowski Mędrzec (155,460 p.)

W żadnym wypadku. To nie jest JavaScript tylko C++ by proponować takie rozwiązania. Nawet w JavaScript wynik operacji z konwersją do string jest o rząd wielkości dłuższy niż nawet zliczenie jedynek. A rozwiązanie z Hamming'iem, pokazuje zalety na większości platform już od 16 bitów.

1	komentarz 8 września 2019 przez manjaro Nałogowiec (37,390 p.) Ale tu nie programujemy najnowszego procesora żeby ścigać się o milionowe części sekundy tylko rozwiązujemy proste zadanie. Prosto łatwo i skutecznie.

komentarz 8 września 2019 przez mokrowski Mędrzec (155,460 p.)

Bitami jest prosto, łatwo i skutecznie a nie "drutem plastrem i sznurkiem".

Litości.... Argumentacja powinna mieć jakiś poziom :-(

Może zobacz jak wygląda rozwiązanie które proponujesz w asemblerze i jaką ma objętość i porównaj.

komentarz 8 września 2019 przez manjaro Nałogowiec (37,390 p.)

Litości...

Ja wiem że twój sposób jest lepszy ale jest dużo trudniejszy w implementacji i zrozumieniu.

A jak sądzę po treści pytania nikt nie potrzebuje tutaj takiego skomplikowanego rozwiązania. Zresztą gdzie w praktyce potrzeba policzyć jedynki w liczbie binarnej? Przecież to jest tylko głupie zadanie na policzenia a nie do zastosowań praktycznych.

komentarz 8 września 2019 przez mokrowski Mędrzec (155,460 p.)

Zresztą gdzie w praktyce potrzeba policzyć jedynki w liczbie binarnej?

To może zerknij do linków w odpowiedziach. Myślę że będziesz wtedy wiedział gdzie to trzeba robić w praktyce. Będziesz zdziwiony.

Przecież to jest tylko głupie zadanie na policzenia a nie do zastosowań praktycznych.

Nie zastanawia Cię to że nawet na poziomie asemblera przewidziano do tego typu "głupich zadań" instrukcje?

W C++ i C, instrukcje operacji bitowych to podstawy programowania.

EOT

komentarz 8 września 2019 przez manjaro Nałogowiec (37,390 p.)

Nie zajmuję się asemblerem, nie znam go i nie mam obowiązku znać.

Autor nie pytał o operacje na bitach tylko o policzenie jedynek.

Twoje porady są dobre dla programistów zajmujących się mikroprocesorami i gdzieś tam jeszcze może, ale tam nikt takich pytań z kolei nie zadaje.