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

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

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

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


binary assembly bit-manipulation
person Mithrax    schedule 14.04.2009    source источник

Ответы (4)


arrow_upward
24
arrow_downward

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

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

Следовательно:

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

ИЗМЕНИТЬ:

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

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

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

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

EDIT: комментарий Бастьена Леонара также хорошо описывает это:

если вы делите (без знака) на 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.

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

person Evan Teran    schedule 14.04.2009
comment
Да, я объяснял, почему вы можете И с y -1, чтобы получить то же значение, что и MOD y. - person Evan Teran; 14.04.2009
comment
@tvanfosson: спасибо за откат, сам собирался это сделать после вашего комментария в другом посте :). - person Evan Teran; 14.04.2009
comment
@ Эван Теран, я вижу, как вы говорите, что они эквивалентны, но я все еще не понимаю, почему это должно быть y - 1? - person Mithrax; 14.04.2009
comment
@Mithrax: если вы разделите (без знака) на 4, вы сдвинете два бита вправо. Таким образом, остаток — это те два бита, которые теряются при делении. 4 - 1 = 11b, то есть маска, которая дает два крайних правых бита, когда вы выполняете И со значением. - person Bastien Léonard; 14.04.2009
comment
@Bastien: хороший способ сказать это, добавлено к моему ответу. - person Evan Teran; 14.04.2009
comment
Спасибо, Эван и все остальные. Я признателен за это. - person mmcdole; 14.04.2009
comment
Запишите x как разложение по степеням двойки и предположите, что y = 2^k для некоторого k. Затем напишите: x = (\Sigma_{m=k}^{\infty} c_m * 2^m) + остаток. Первый член кратен y, а «Остаток» ‹ y. Итак, x mod y эквивалентно «Остаток». Но это всего лишь битовый шаблон x&y-1. - person Derek E; 15.04.2009

arrow_upward
5
arrow_downward

(х и 3) == 0

В.р.т. язык ассемблера, используйте TST, если доступно, в противном случае И, и проверьте нулевой флаг.

person starblue    schedule 14.04.2009
comment
@John - да, это 0 - это произведение 0 x 4. en.wikipedia.org /wiki/Несколько_(математика) - person tvanfosson; 14.04.2009

arrow_upward
3
arrow_downward

В сборке x86:

    test eax, 3
    jnz not_multiple_of_4

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

not_multiple_of_4:
    ; ...
person Bastien Léonard    schedule 14.04.2009

arrow_upward
1
arrow_downward

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

person Hldev Zkran    schedule 14.04.2009
comment
Большинство машин отслеживают только последний сдвинутый бит, или MIPS, о котором спрашивает OP, вообще не имеет флагов. Если вы хотите использовать сдвиг, вы должны сдвинуть влево на 32-2, чтобы сдвинуть все остальные биты, оставив только младшие 2 бита, которые могут быть ненулевыми. Или, лучше, изолируйте их с помощью AND, например x & 3 - person Peter Cordes; 03.06.2020