Jak mogę sprawdzić, czy liczba jest wielokrotnością czterech, używając tylko operatora logicznego AND?

Question

Wprowadzam w błąd przy programowaniu w języku asemblerowym i jestem ciekawa, jak mogłem stwierdzić, czy liczba jest wielokrotnością 4 za pomocą operatora logicznego ORAZ?

Wiem, jak to zrobić, używając instrukcji "div" lub "reszta", ale próbuję to zrobić z manipulacją bitową liczby/słowa.

Czy ktoś może wskazać mi właściwy kierunek? Używam MIP, ale odpowiedź agnostyczna na język jest w porządku.

Answer 1

Cóż, aby wykryć, czy liczba jest wielokrotnością innej, wystarczy wykonać numer x MOD y. Jeśli wynikiem jest 0, to jest to wielokrotność.

Prawdą jest również, że dla każdego y że jest potęgą 2, (x MOD y) jest równoważna (x AND (y - 1)).

Dlatego:

IF (x AND 3) == 0 THEN 
    /* multiple of 4 */ 

EDIT:

ok, chcesz wiedzieć dlaczego(x MOD y) == (x AND (y - 1)) gdy y jest potęgą 2. Zrobię najlepiej wyjaśnić.

Zasadniczo, jeśli liczba jest potęgą 2, to ma ona ustawiony pojedynczy bit (ponieważ binarny jest podstawą 2). Oznacza to, że wszystkie dolne bity są rozbrojone. Na przykład: 16 == 10000b, 8 == 1000b, itp.

Jeśli odejmiesz 1 od dowolnej z tych wartości. W efekcie ustawiony bit jest nieustawiony, a wszystkie bity poniżej są ustawiane.

15 = 01111b, 7 = 0111b itd. W zasadzie tworzy maskę, która może być użyta do sprawdzenia, czy został ustawiony dowolny z niższych bitów. Mam nadzieję, że było jasne.

EDIT: komentarz Bastien Leonard obejmuje go zbyt dobrze:

jeśli podzielić (unsigned) przez 4, przesuwasz dwóch bitów w prawo. Tak więc pozostała część to te dwa bity, które tracą po podzieleniu . 4 - 1 = 11b, , czyli maska, która daje dwa najdokładniejsze bity , gdy ORAZ to z wartością .

EDIT: zobaczyć aktualizacja ewentualnie jaśniejszych wyjaśnień: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

Obejmuje wykrywania uprawnień i 2 i używając jako szybka operacji modulo, jeśli jest potęgą 2.

Answer 2

(x & 3) == 0

W.r.t. asembler, użyj TST, jeśli jest dostępny, w przeciwnym razie ORAZ sprawdź flagę zero.

Answer 3

Liczba jest wielokrotnością 4, jeśli jej dolne 2 bity to 0, więc wystarczy przesunąć liczbę dwukrotnie w prawo i sprawdzić przesunięte bity na 0.

Answer 4

W zespole x86:

test eax, 3 
    jnz not_multiple_of_4 

    ; action to be taken if EAX is a multiple of 4 

not_multiple_of_4: 
    ; ...