Как используя логические операции определить делится ли число на 4 на 8

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

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

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

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

4 ответа

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

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

РЕДАКТИРОВАТЬ:

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

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

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

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

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

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

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

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

Правило признака делимости на 4 с примерами

При упрощении выражений необходимо знать некоторые особенности или правила с примерами. Признаки делимости на 4 вызывают сложности у учеников в 5 классе. Для изучения этой темы специалисты предлагают использовать научный подход, который основан на психофизиологических особенностях работы головного мозга. Он включает ознакомление с основными элементами теории и алгоритмом.

Общие сведения

Деление — арифметическая операция, позволяющая найти один из множителей при их произведении. Иными словами, деление является обратным действием относительно умножения. Записывается оно следующим образом: U/T=V. Далее следует подробно разобрать каждый из элементов операции:

1. U — делимое (исходная величина, представляющая целое или дробное число).
2. T — делитель (значение, показывающее количество равных частей, на которые требуется разделить первоначальное значение).
3. V — результат операции.

Если провести аналогию с умножением, то компоненты можно назвать по-другому: U — произведение, T и V — I и II множители соответственно. Следует отметить, что операция деления проверяется при помощи произведения.

Например, нужно поделить 12 на 4. Записывать действие необходимо в виде математического числового выражения, т. е. 12/4. Результат эквивалентен значению 3. Чтобы проверить правильность нахождения частного, необходимо осуществить произведение «4*3».

Признаки делимости на 4

Для деления искомого числа на четверку нацело специалисты разработали специальный алгоритм. Он позволяет быстро определить, какое число делится на 4. Он имеет следующий вид:

1. Проверить величину на четность. Если число — четное, то нужно перейти ко второму пункту.
2. Отсеять две последние цифры.
3. Значение, полученное во втором пункте, должно нацело делиться на четверку.

Исходя из методики, можно сформулировать такое свойство, позволяющее узнать, делится ли исходное значение на 4: величина на четверку делится в том случае, когда является четной и число, образованное разрядами десятков и единиц, можно поделить на это значение без остатка.

Пример реализации

Для реализации методики необходимо доказать кратность числа 213 четверке. Это осуществляется таким образом:

1. Записать величину: 213.
2. Проверить ее на четность: 213 — нечетное значение.
3. Вывод: число 213 на четверку нацело поделить невозможно.

Далее необходимо разобрать другой пример деления 212 на 4. Проверка кратности осуществляется следующим образом:

1. Записать число: 212.
2. Проверить на четность: 212 — четное, т. к. последний разряд заканчивается на двойку.
3. Число, образованное из двух последних цифр: 12.
4. Вывод: 212 можно без остатка поделить на 4, поскольку значение является четным, а две последние элементы разрядной сетки делятся на четверку.

Если выполнить операцию «212/4» при помощи калькулятора, то можно получить целочисленное значение, которое равно 53. Чтобы понять принцип действия алгоритма, нужно придумать любое число, и попытаться поделить его на четверку. Например, нужно разделить 4325624 на 4. Для этого требуется сначала выяснить кратность искомого числа четырем. Решать задачу нужно таким образом:

1. Записать величину: 4325624.
2. Определить четность: четное, поскольку заканчивается на 4.
3. Взять последние 2 цифры: 24. Они делятся на 4, поскольку 4*6=24.

Далее требуется на калькуляторе или в столбик осуществить операцию деления, результатом которой будет число «1081406».

Таким образом, чтобы поделить любое числовое значение на четверку нужно проверить его четность, а также целочисленное деление на искомый делитель величины, образованной двумя последними цифрами.

Урок 31 — 35
Арифметические и логические (битовые) операции. Маски. Арифметические и логические (битовые) операции. Маски
§26. Особенности представления чисел в компьютере. §27. Хранение в памяти целых чисел. § 28. Операции с целыми числами. §29. Хранение в памяти вещественных чисел

1. Покажите на примере, как складываются два положительных целых числа, записанные в 8-разрядные ячейки. Что изменится, если числа будут отрицательными?
2. Что такое дополнительный код? Сформулируйте правила получения дополнительного кода числа.
3. При каких комбинациях знаков слагаемых в результате сложения может возникнуть переполнение?
4. Какое устройство выполняет в компьютере сложение? Вспомните, что вы знаете об этом устройстве.
5. Почему не нужно разрабатывать специальное устройство для вычитания целых чисел?
6. Перемножьте столбиком два положительных целых числа в двоичной системе счисления. Изменится ли алгоритм выполнения операции, если у одного из сомножителей поменять знак?
7. Почему коды чисел со знаком и без знака нужно сравнивать по-разному?
8. Что такое поразрядные операции? Приведите примеры.
9. Почему арифметические операции нельзя отнести к поразрядным?
10. Что такое маска?
11. Как, используя маску, сбросить определённый бит (записать в него 0)?
12. Напишите значение маски для того, чтобы сбросить в 16-разрядном числе 2 младших бита, не изменяя все остальные. Какую логическую операцию нужно для этого использовать?
13. Как, используя маску, установить определённый бит?
14. Напишите значение маски для того, чтобы установить в 16-разрядном числе 2 старших бита, не изменяя все остальные. Какую логическую операцию нужно для этого использовать?
15. Как, используя логические операции, определить, делится ли число на 4? На 8?
16. В каких практических задачах можно применять установку или сброс битов двоичного кода?
17. Каковы возможности операции «исключающее ИЛИ»?
*18. Попробуйте придумать алгоритм шифрования кода с помощью операции «исключающее ИЛИ». Постарайтесь предложить простой алгоритм изменения маски, а не просто использовать константу.
19. Прочитайте ещё раз материал, связанный с переполнением при сложении. Какой логической операцией можно определить, совпадают или нет биты S’ и S?
20. Какую роль играет операция «НЕ» при получении отрицательных чисел?
21. Как выполнить инверсию всех битов, не используя логическую операцию «НЕ»?
22. Что такое сдвиг? Какие вы знаете виды сдвига?
23. Как обрабатываются самый старший и самый младший биты при различных типах сдвига?
24. Покажите на примерах, что сдвиг влево двоичного кода удваивает число, а сдвиг вправо — уменьшает вдвое.
25. Почему логический сдвиг не годится для уменьшения в два раза отрицательных чисел? Как работает арифметический сдвиг?
26. Почему не требуется арифметический сдвиг влево?
*27. Выведите правило вычисления результата арифметического сдвига отрицательного нечётного числа на один разряд вправо. Проверьте, применимо ли это правило к положительным нечётным числам. Как упрощается формула для чётных исходных значений?
28. Где могут применяться сдвиги?

Подготовьте сообщение

а) «Битовые логические операции»
б) «Шифрование с помощью операции «исключающее ИЛИ»»
в) «Применение сдвигов»

Следующая страница Задачи

Cкачать материалы урока