Как я могу определить, является ли число кратным четырем, используя только логический оператор AND?

Question

Я возиться с программированием на ассемблере, и мне любопытно, как я могу определить, кратно ли число 4, используя логический оператор AND?

Я знаю, как это сделать, используя команды "div" или "remainder", но я пытаюсь сделать это с помощью битовых манипуляций с числом / словом.

Кто-нибудь может указать мне правильное направление? Я использую MIP, но не зависящий от языка ответ - хорошо.

Answer 1

Ну, чтобы определить, является ли число кратным другому, вам просто нужно сделать x MOD y. Если результат равен 0, то он даже кратен.

Также верно, что для каждого y, равного 2, (x MOD y) эквивалентно (x AND (y - 1)).

Таким образом:

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

EDIT:

хорошо, вы хотите знать , почему (x MOD y) == (x AND (y - 1)), когда y является степенью 2. Я сделаю все возможное, чтобы объяснить.

По сути, если число является степенью 2, то для него установлен один бит (поскольку двоичное является основанием 2). Это означает, что все младшие биты не установлены. Так например: 16 == 10000b, 8 == 1000b и т. Д.

Если вы вычли 1 из любого из этих значений. В результате получается, что установленный бит не установлен, а все биты ниже него установлены.

15 = 01111b, 7 = 0111b и т. Д. Таким образом, в основном это создает маску, которая может использоваться для проверки, был ли установлен какой-либо из младших битов. Я надеюсь, что это было ясно.

РЕДАКТИРОВАТЬ: Комментарий Бастиена Леонара также хорошо это освещает:

если вы разделите (без знака) на 4, вы сдвинуть два бита вправо. Таким образом Остальные те два бита, которые получают потерян, когда вы разделите. 4 - 1 = 11b, то есть маска, которая дает два самые правые биты, когда вы И это с значение.

РЕДАКТИРОВАТЬ: см. Эту страницу для более четких объяснений: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

Он охватывает обнаружение степеней 2 и использование AND в качестве быстрой операции по модулю, если это степень 2.

Answer 2

(х & 3) == 0

W.r.t. ассемблер, используйте TST, если доступно, в противном случае AND, и отметьте нулевой флаг.

Answer 3

В сборке x86:

    test eax, 3
    jnz not_multiple_of_4

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

not_multiple_of_4:
    ; ...

Answer 4

Число кратно 4, если его младшие 2 бита равны 0, поэтому вы можете просто сдвинуть число вправо дважды и проверить сдвинутые биты на 0.