Skocz do zawartości

zwracanie ilości jedynek w słowie binarnym


I am Lord

Rekomendowane odpowiedzi

@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;

Odnośnik do komentarza
Udostępnij na innych stronach

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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

Odnośnik do komentarza
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się
  • Ostatnio przeglądający   0 użytkowników

    • Brak zarejestrowanych użytkowników przeglądających tę stronę.
×
×
  • Dodaj nową pozycję...