zwracanie ilości jedynek w słowie binarnym

[I am Lord]

Jest jakiś prosty sposób by z danego słowa binarnego zwrócić ile jest jedynek?

 

Np mam takie słowo:

11101 i chciał bym by taka funkcja zwróciła mi 4

01101 = 3

11111 = 5 itd.

[tramur]

1. Deklarujesz suma = 0; a = liczba
2. Zapętlasz dopóki a != 0
   • Jeżeli a & 1 jest prawdą (myślę, że Game Maker ma operatory bitowe) to suma+=1
   • a = a div 2 (lub a = a >> 1)
3. Masz teraz ilość jedynek

Nie wiem, czy jest prostszy sposób, zważywszy na tą złożoność liniową.

[ediepl]

GML

var _i, _txt;

_i = 0;

_txt = argument0 // np "11101011"

while(_txt != "")

{

if string_char_at(_txt, 1) = "1" _i += 1;

_txt = string_copy(_txt, 1, string_length(_txt)-1);

}

return _i;

[I am Lord]

@up właśnie zapomniałem napisać że nie ma być na stringu. Spróbuje zrobić to co tramur podpowiada.

 

Edit:

Ok Tramura funkcja działa poprawnie.

 

Jak by ktoś też chciał no to proszę:

GML

// Zwraca ilosc jedynek w slowie binarnym

// argument0 - integer

var _a, _b;

_a = argument0;

_b = 0;

while ( _a != 0 )

{

if ( _a & 1 ) _b += 1;

_a = _a >> 1;

}

return _b;

[Platyna]

Da się liniówkę zamortyzować. Rozwiązanie o złożoności proporcjonalnej do ilości jedynek:

 

GML

var _a;

_a = argument0;

_wynik = 0;

 

while (_a != 0)

{

_wynik+=1;

_a -= (_a-(_a&(_a-1)));

}

 

return _wynik;

 

Ta dziwna linijka od razu usuwa pierwszą od prawej jedynkę. W końcu zostaną same zera. : )

A tak poza tym to ciężko mówić o tym "liniówka". Raczej bardziej "mówiące" jest O(log a). Skoro nie rozważamy stringów to lepiej podać złożoność w zależności od liczby której zapis rozważamy. Złożoność funkcji podaje się w zależności od danych argymentów.

[I am Lord]

No twoje też działa i jest nawet nieco szybsze.

[Snake]

Można jeszcze wydajniej to wyliczać pewnym strasznie wyglądającym algorytmem::

GML

argument0 -= ((argument0 >> 1) & $55555555);

argument0 = (((argument0 >> 2) & $33333333) + (argument0 & $33333333));

argument0 = (((argument0 >> 4) + argument0) & $0f0f0f0f);

argument0 += (argument0 >> 8);

argument0 += (argument0 >> 16);

 

return (argument0 & $3f);

source

[Platyna]

Mistrzostwo! Rozgryzę czemu to działa. : D

[I am Lord]

Magiczne algorytmy? Taa to dobry tytuł dla tej stronki :D