Логические битовые операции
Осторожно! Статья пока сырая, ляпы наверняка есть, возможно серьёзные.
Когда складывал главы для витков, забыл одну из важнейших базовых тем. И, к сожалению, несмотря на то, что эта тема тоже входит в обязательную школьную программу, на практике большинство людей даже на поверхностном уровне являются натуральными чайниками =(.
Мы лишь мизинцем левой ноги коснулись логических операций (команды test, xor и and разок использовали). Теперь пришло время разобраться от самых корней. Как же всё-таки из кучки обычных выключателей выпекают компьютеры?
Вспомните простейшую схему:
батарейка, 2 выключателя и лампочка. Поскольку выключатели в цепи располагаются последовательно, лампочка будет гореть только если вкл. и "A", и "Б". Эта схема в логических терминах так и называется - "И". Если поставить выключатели "А" и "Б" параллельно, логика меняется. Тут достаточно включить или "A", или "Б". Соответственно называется эта схема "ИЛИ". На вопрос: "Кто больше нравится - брюнетки или блондинки?", настоящий мужчина всегда отвечает - "да". Замените лампочку одним битом регистра, а выключатели - битами операндов, и перед вами окажется самая простая трактовка механизма работы двух основных логических команд Ассемблера: Команда AND ПроисхождениеОт англ. слова and - и ФорматAND приёмник, источник ДействиеПобитовое логическое действие "И" Если соответствующие биты обоих операндов равны 1, то результат равен 1. Во всех остальных случаях результат =0. Команда OR ПроисхождениеОт англ. слова or - или ФорматOR приёмник, источник ДействиеПобитовое логическое действие "ИЛИ" Если соответствующие биты обоих операндов равны 0, то результат равен 0. Во всех остальных случаях результат =1. Все 4 варианта переключения битов выглядят так: 0101 AND 1001 ---- Результат: 0001 0101 OR 1001 ---- Результат: 1101 Думаю, это несложно понять. Теперь осталось только закрепить на практике, разобрав несколько жизненных примеров. Получаем из символьного кода цифры её значение (в prax14 делали так с одним байтом, теперь сразу 4): mov EAX, 31323334h ; загружаем ASCII-коды символов "1234" and EAX, 0F0F0F0Fh ; в EAX будет 01020304h Таким образом, мы "убиваем" старшую тетраду каждого байта и не изменяем младшую. Разумеется, так же можно обнулять и E-часть регистра: mov EAX, 12345678h ; загружаем любое число and EAX, 0000FFFFh ; в EAX будет 00005678h И даже весь регистр: and EAX, 0 ; в EAX будет 0 Можно сделать число чётным: mov EAX, 77777777h ; загружаем любое число and EAX, -2 ; -2 это ведь 11111111 11111111 11111111 11111110b ; Теперь в EAX обязательно чётное число ("очётили" в младшую сторону) Можно сделать число кратным степени двойки: mov EAX, 77777777h ; загружаем любое число and EAX, -4 ; -4 это ведь 11111111 11111111 11111111 11111100b ; Теперь в EAX число, обязательно кратное 4 в младшую сторону and EAX, -10h ;-10h это ведь 11111111 11111111 11111111 11110000b ; А теперь обязательно кратное 16 в младшую сторону Хорошо, а что может делать OR? Например, в обратную сторону получаем символьный код цифры из значения: mov EAX, 01020304h ; загружаем значения or EAX, 30303030h ; в EAX будут ASCII-коды символов "1234" Таким образом, мы записываем в старшую тетраду каждого байта тройку и не изменяем младшую тетраду. Соответственно, легко сделать число нечётным: mov EAX, 88888888h ; загружаем некоторое число or EAX, 1 ; Теперь в EAX обязательно нечётное число ("онечётили" в большую сторону) То есть можно включить любой нужный бит или сразу несколько битов: or EAX, 10101010 10101010 10101010 10101010b Обычно это делается для того, чтобы задавать параметры или состояния, которые предварительно описывают в константах, примерно так: ICON_FLAG equ 1 ; 0001b OPEN_FLAG equ 2 ; 0010b EDIT_FLAG equ 4 ; 0100b X_FLAG equ 8 ; 1000b ... or dword ptr [Status], EDIT_FLAG ; вкл. состояние редактирования (бит № 2) Бинарники любят спорить. Они спорят так часто, что уже давно знают результат любого спора. И всё равно они спорят. Спорят даже в тех случаях, когда результат не меняется. Впрочем, иногда цель спора не очевидна. Возможно, молодой бинат просто хочет произвести впечатление на красотку с флагом. Чаще всего команду OR используют хитрее. Проверить регистр на ноль можно так: or EAX,EAX ; не изменяет содержимое регистра, но включает ZF (флаг нуля), если EAX=0 Думайте сами, решайте сами... Помню, ещё в детстве очень хотел сделать так, чтобы свет в спальне можно было включать/выключать, не вставая с кровати ИЛИ(!) при входе в комнату. Большинство сразу же подумает: пультик - лучшее решение. А вот и нет! На самом деле при помощи логики можно обойтись без всяких сложных электронных наворотов простыми средствами. Давайте размышлять. Если подключить выключатели последовательно подобно схеме AND, то нужно будет включить оба выключателя, чтобы свет загорелся. Такое решение сделает неудобным процесс включения света. Если же подключить выключатели параллельно - как OR, то придётся выключать оба выключателя, чтобы свет погас. Соответственно, придётся прикладывать лишние усилия, чтобы выключать свет. Выходит, наша задача состоит в том, чтобы исключить недостатки и последовательной, и параллельной схемы. Или, выражаясь языком наполовину полного стакана, нужно объединить преимущества этих двух подключений. Создать некий промежуточный вариант. Параллельно-последовательное включение-выключение. К сожалению, сам я когда-то поленился придумать этот велосипед самостоятельно и теперь так никогда и не узнаю, сколько времени у меня ушло бы на изобретение (думать, что я бы так и недопёр, даже не хочется =). Завидую тем, кто ещё не знает решения. Очень рекомендую взять листок бумаги и рисовать, рисовать, рисовать до тех пор, пока не сможете найти простое красивое подключение. Пускай это займёт час, два и больше. Люди, которые допёрли самостоятельно, говорят, что удовольствие того стоит. ... На случай если за два часа ничего не вышло, открывайте первую подсказку. ПОДСКАЗКА №1: В схеме всего 2 переключаемых элемента. На следующий день дополнительные подсказки =). ПОДСКАЗКА №2: Это не совсем выключатели. ПОДСКАЗКА №3: Это два переключателя. У каждого переключателя только 2 состояния. Ну и исключительно, чтобы убедиться в правильности решения, ОТВЕТ: А теперь распишите, пожалуйста, таблицу всех возможных значений этой схемы нулями и единицами. Получилось? Отлично. Вспомним команду, при помощи которой мы шифровали строку в prax09 XOR - логическое побитовое, исключающее ИЛИ. Работает подобно OR, с одним лишь отличием: XOR выключает бит, если в обоих операндах он был включен. Мы уже рассматривали таблицу значений XOR в нулевом витке, но сейчас самое время повторить: 0101 XOR 1001 ---- 1100 Сравните таблицу значений XOR с таблицей параллельно-последовательной схемы, которую вы только что расписали. Заметили? Должно быть, оно же, но только с противоположным результатом. Для того чтобы параллельно-последовательная схема представляла логическое действие, исключающее ИЛИ, достаточно сделать простое допущение: лампочка горит = 0 лампочка погасла = 1 Но если во всей схеме процессора мы приняли положительную трактовку сигнала (лампочка горит = 1), то на практике этот фокус не прокатит. Придётся чуточку усовершенствовать саму схему с помощью следующего логического элемента... NOT – всё наоборот Самое очевидное действие – НЕ (в смысле отрицание). Операнд только один, а таблица значений состоит всего из двух возможных комбинаций: 01 NOT 10 Так и команда ассемблера NOT имеет только один операнд. В результате её действия значение каждого бита в операнде будет инвертировано. Фактически логика "НЕ" реализуется в обычном электромагнитном реле. Когда ток подаётся на катушку, контакты выключателя размыкаются, когда тока нет – контакты замыкаются. Понятно, что обычные выключатели, переключатели и реле в далёком прошлом. Современный техпроцесс позволяет разместить на кремниевых пластинках миллионы переключаемых элементов на каждый см2 и это только на один слой, а слоёв может быть больше, чем в моих любимых круасанах. В общих чертах базовую логику мы уже рассмотрели. Все вычисления (такие как сложение/вычитание, умножение/деление и дальше, вплоть до самых сложных математических действий) ЦП реализует путём комбинации всё тех же переключаемых элементов, то есть в основе лежат именно AND, OR, XOR и NOT. Честно признаюсь: сам я глубоко не вникал даже в принципиальную схему команды ADD, но в общих чертах каждому необходимо понимать, как на базе логических элементов выстроены сложные компоненты, присутствующие внутри микросхем. И здесь вам поможет одна замечательная классическая книга Эндрю Таненбаума "Архитектура Компьютера". В 2007 году вышло 5-е издание на русском (доступно в сети). Обязательно загляните в неё! Мне хватило беглого осмотра картинок из главы 3 "Цифровой логический уровень" =). А когда устанете читать про вентили, ловушки и прочую техническую хрень, вот вам онлайн-игруха под названием XOR: http://liszkay.hu/xor/ Цель: удалить все кубики, пробел переворачивает курсор... Впрочем, есть игрушка, в 100 раз прикольнее, и тема как раз наша: BloXORz Развлекайтесь =). Наигрались? Тогда отдохните и возвращайтесь сюда со свежими мозгами и глазами. Будем решать одну головоломку, куда как круче детских игрушек. Раз, раз, проверка Но перед этим проверим, насколько вы прониклись темой. Несколько элементарных вопросов, на которые каждый должен ответить относительно быстро: 1. Что изменит следующая команда? and EAX,EAX ОТВЕТ: Состояние битов регистра EAX не изменится, может измениться только регистр флагов. 2. Команда TEST (если забыли, см. описание в нулевом витке) по какой логике работает? ОТВЕТ: По логике команды AND, но результат вычислений мнимый, и опять же - изменяется только состояние регистра флагов. 3. Какая команда использовалась бы для выборочного включения флагов в регистре Eflags, если бы у него было имя обращения и можно было бы явным образом включать биты этого регистра? А выключать? ОТВЕТ: Для включения подойдёт or, а для выключения - and. 4. Теперь решим задачку особой сложности (только для высокопоставленных дипломатов bit-миссии). NOT – всё наоборот, а давайте сделаем "не всё наоборот". Задача: сделать выборочное битовое сито для NOT (битовую маску). То есть создать такой код, чтобы можно было инвертировать лишь определённую часть значения. Вход: EAX – значение, EDX – маска Выход: будут инвертированы только те биты EAX, которые были включены в EDX Ход решения: Итак, у нас на входе 2 операнда EAX и EDX, а на выходе один-единственный результат. Давайте попробуем составить таблицу преобразований битов: EAX 0101 EDX 1001 ---- Выход: 1100 Результат: ТЪфу, ты ж, блин! Опять XOR получился! xor EAX,EDX =))) Наблюдая за окружающими, Юнга заметил, что радость местным жителям приносит вовсе не прелесть острова. Оказалось, что все, кто остался, все, ставшие аборигенами, постоянно учатся. На острове исключительно в процессе обучения можно испытать невероятное чувство блаженства. Причём если от учёбы толку нет, если просветление мозгов вовремя не наступает, эйфория сменяется самой настоящей ломкой. В конце концов, Юнга поговорил об этом с Учителем. - Эта звезда, - Учитель указал рукой на небо, - этот пляж, - Учитель просеял песок сквозь пальцы... - Сам остров пронизан силой познания. Мы давно изучаем этот феномен. Биологи утверждают, что метаболизм мыслящих существ здесь временно меняется. Физики говорят про уникальное излучение, про эффект резонанса собственных колебаний песчинок и звезды... Хотя это всего лишь очередная теория. Так или иначе, здесь остаются только самые способные ученики. Правда, у них появляется новая проблема... Долгожданный новый prax Всё, хватит шуток, вот она - обещанная головоломка. Вопрос: как посчитать все включённые биты (то есть единички) в EAX? Поясню задачу, если вдруг непонятна суть. Рассмотрим для примера конкретное число - 270h, в двоичном виде будет: 1001110000 Здесь 4 единички. А теперь попросите свой компьютер сосчитать их. Задача, между прочим, - не просто забавная головоломка, но и практически полезная штука (для чего, расскажу в другой главе). Не даром инженеры Интел решили-таки добавить отдельную команду POPCNT для её решения, правда, эта команда пока что есть далеко не во всех процессорах (только с поддержкой нового набора инструкций SSE4.2). Но мы и сами не безрукие, найдём решение. Как обычно, единого правильного ответа нет, их целая куча, так что каждый может подобрать один из вариантов и найти в нём свои плюсы. Сегодня я расскажу вам об одном классическом методе. Он основан на двух китах: 1) правило "разделяй и властвуй". 2) комп – это сплошные переключатели. Долблю, как дятел, одно и то же, а что делать: нового ничего нет =). Итак, поехали. Пока просто наблюдайте за ходом мыслей и наслаждайтесь эстетикой решения. Согласно принципу №1, задачу надо разделить на такие мелкие кусочки, что каждый из них будет решаться тривиально. Вспомните "адскую" главу "Системы счисления, виток1". Решая третью задачу из prax14, мы рассматривали число 5678 как полином (многочлен) и, загнав его в глубокие скобки, привели равенство как раз к такому тривиальному действию. Сейчас будет нечто подобное, только с другого ракурса (без всяких формул). К примеру, возьмём число D23Fh, в бинарном виде оно достаточно разнообразно: 1101 0010 0011 1111 Задачу можно раздробить на набор одних и тех же постоянно повторяющихся действий. В некоторых случаях удобно было бы даже создать функцию, которая в ходе решения задачи многократно вызывает сама себя. ... Такой подход называется рекурсия. Рекурсивные действия хорошо воспринимаются в виде ветвистого графа (дерева): Каляка-маляка из детсада, а не граф! Почему? Да потому что в верхней строке число в двоичном представлении, а дальше идут десятичные вычисления. Извращение сплошное! Но зато воспринимается как дважды два четыре =), а не 1+1=10b... И всё-таки нельзя так. Давайте рассмотрим те же действия, но только в бинарном виде: Вот, так уже лучше. Что нам даёт такое дробление? Даёт элементарную операцию в каждом "кубике". В нашем случае эту операцию не стоит оформлять в виде отдельной функции и даже в цикл её закручивать неэффективно, потому что количество шагов ничтожно по меркам ЦП. Но всё равно в общем смысле дальнейшее решение считается рекурсивным. Выразим на Ассемблере такую элементарную операцию только для двух бит (одного верхнего "квадратика"): ;Вход: в EAX учитываются только два младших бита ;Выход: в EAX сумма единичных значений двух младших бит mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг. 1-й бит займёт позицию нулевого and EDX,1 ; накладываем маску на все биты, кроме младшего (выкл. всё, нулевой бит не трогать) and EAX,1 ; аналогично для другого регистра add EAX,EDX ; а теперь просто складываем бывший первый бит и нулевой Таким нехитрым способом мы имеем сумму одного из четырёх возможных вариантов: 1+1, или 1+0, или 0+1, или 0+0. Всё больше и больше я буду отсылать вас к полноценному справочнику команд Ассемблера. Вот и про shr (от англ. shift right) скажу лишь то, что она похожа на команду ror, с которой мы уже знакомы, только shr не прокручивает биты, а просто вытесняет вправо. Не сложно догадаться, что существует и обратная команда - shl, про которую тоже рекомендую читать в справочнике. Теперь давайте подумаем, а можно ли выполнить действие сложения одновременно для всех пар рядом стоящих бит в регистре EAX? Можно. Можно одновременно решить сразу всю верхнюю строку графа. Причём изменение в коде настолько мелкое, что даже удивляет простота решения: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг and EDX,01010101010101010101010101010101b ; в копии накладываем маску на все старшие биты в парах and EAX,01010101010101010101010101010101b ; аналогично для другого регистра add EAX,EDX ; а теперь точно так же складываем Последняя команда сложения в данном случае складывает все "бывшие старшие" и младшие биты во всех парах и на выходе у нас в регистре EAX находится 16 суммарных значений всех единичных бит по парам. Обычное сложение работает потому, что нам наверняка известно: в паре бит может быть максимум 1+1 единичек, и эти единички займут те же самые два бита в виде 10b. Значит, переноса битов в старшие разряды быть просто не может. К следующему шагу переходите после полного осмысления кода. Согласно графу на следующем этапе надо укрупнить суммы шестнадцати пар до сумм восьми тетрад. Опять вернёмся на уровень минимальной единицы, теперь уже одной тетрады: ;Вход: в EAX учитывается только младшая тетрада ;Выход: в EAX сумма единичных значений двух пар младшей тетрады mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,11b ; биты №0 и №1 не трогать, всё остальное выкл. and EAX,11b ; аналогично для другого регистра add EAX,EDX ; складываем бывшую первую пару и нулевую Вникли? Здорово, правда? Решение для целого регистра идёт уже по накатанной: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,00110011001100110011001100110011b ; накладываем маску на все старшие пары and EAX,00110011001100110011001100110011b ; аналогично для другого регистра add EAX,EDX ; складываем пары Теперь в регистре суммы по тетрадам. Следующие шаги (сумма всех тетрад до байта, сумма всех байт до слова и сумма слов) решаются аналогично. С этого места лучше начать кодировать и думать самостоятельно. Попробуйте довести обработку EAX до финального результата. Задача, кстати, не детская. Программистов высшей квалификации на собеседованиях в крупнейших корпорациях по всему миру часто просят решить этот или похожий пример. Далеко не каждый соискатель способен сознательно описать шаги рекурсивного решения. И не думайте, что я такой гениальный: изобрёл алгоритм. Мозгов Bitfry'я хватает только на то, чтобы найти решение в книге. В данном случае мне помогли mr.Гугел и книга Hacker's Delighit (Г. Уоррен "Алгоритмические трюки для программистов"). Надеюсь, мои труды по разжёвыванию этой задачи не прошли даром. Надеюсь, хотя бы единицы начинающих читателей теперь смогут суммировать единицы в EAX самостоятельно. На всякий случай, полный код решения (без какой-либо оптимизации) будет лежать в prax16. Очень надеюсь, что он вам не понадобится. А в следующей главе, наверное, будем писать первое окошко для Windows. Bitfry <<предыдущая глава следующая глава>> Вернуться на главную
батарейка, 2 выключателя и лампочка.
Поскольку выключатели в цепи располагаются последовательно, лампочка будет гореть только если вкл. и "A", и "Б". Эта схема в логических терминах так и называется - "И".
Если поставить выключатели "А" и "Б" параллельно,
логика меняется. Тут достаточно включить или "A", или "Б". Соответственно называется эта схема "ИЛИ". На вопрос: "Кто больше нравится - брюнетки или блондинки?", настоящий мужчина всегда отвечает - "да". Замените лампочку одним битом регистра, а выключатели - битами операндов, и перед вами окажется самая простая трактовка механизма работы двух основных логических команд Ассемблера: Команда AND ПроисхождениеОт англ. слова and - и ФорматAND приёмник, источник ДействиеПобитовое логическое действие "И" Если соответствующие биты обоих операндов равны 1, то результат равен 1. Во всех остальных случаях результат =0. Команда OR ПроисхождениеОт англ. слова or - или ФорматOR приёмник, источник ДействиеПобитовое логическое действие "ИЛИ" Если соответствующие биты обоих операндов равны 0, то результат равен 0. Во всех остальных случаях результат =1. Все 4 варианта переключения битов выглядят так: 0101 AND 1001 ---- Результат: 0001 0101 OR 1001 ---- Результат: 1101 Думаю, это несложно понять. Теперь осталось только закрепить на практике, разобрав несколько жизненных примеров. Получаем из символьного кода цифры её значение (в prax14 делали так с одним байтом, теперь сразу 4): mov EAX, 31323334h ; загружаем ASCII-коды символов "1234" and EAX, 0F0F0F0Fh ; в EAX будет 01020304h Таким образом, мы "убиваем" старшую тетраду каждого байта и не изменяем младшую. Разумеется, так же можно обнулять и E-часть регистра: mov EAX, 12345678h ; загружаем любое число and EAX, 0000FFFFh ; в EAX будет 00005678h И даже весь регистр: and EAX, 0 ; в EAX будет 0 Можно сделать число чётным: mov EAX, 77777777h ; загружаем любое число and EAX, -2 ; -2 это ведь 11111111 11111111 11111111 11111110b ; Теперь в EAX обязательно чётное число ("очётили" в младшую сторону) Можно сделать число кратным степени двойки: mov EAX, 77777777h ; загружаем любое число and EAX, -4 ; -4 это ведь 11111111 11111111 11111111 11111100b ; Теперь в EAX число, обязательно кратное 4 в младшую сторону and EAX, -10h ;-10h это ведь 11111111 11111111 11111111 11110000b ; А теперь обязательно кратное 16 в младшую сторону Хорошо, а что может делать OR? Например, в обратную сторону получаем символьный код цифры из значения: mov EAX, 01020304h ; загружаем значения or EAX, 30303030h ; в EAX будут ASCII-коды символов "1234" Таким образом, мы записываем в старшую тетраду каждого байта тройку и не изменяем младшую тетраду. Соответственно, легко сделать число нечётным: mov EAX, 88888888h ; загружаем некоторое число or EAX, 1 ; Теперь в EAX обязательно нечётное число ("онечётили" в большую сторону) То есть можно включить любой нужный бит или сразу несколько битов: or EAX, 10101010 10101010 10101010 10101010b Обычно это делается для того, чтобы задавать параметры или состояния, которые предварительно описывают в константах, примерно так: ICON_FLAG equ 1 ; 0001b OPEN_FLAG equ 2 ; 0010b EDIT_FLAG equ 4 ; 0100b X_FLAG equ 8 ; 1000b ... or dword ptr [Status], EDIT_FLAG ; вкл. состояние редактирования (бит № 2) Бинарники любят спорить. Они спорят так часто, что уже давно знают результат любого спора. И всё равно они спорят. Спорят даже в тех случаях, когда результат не меняется. Впрочем, иногда цель спора не очевидна. Возможно, молодой бинат просто хочет произвести впечатление на красотку с флагом. Чаще всего команду OR используют хитрее. Проверить регистр на ноль можно так: or EAX,EAX ; не изменяет содержимое регистра, но включает ZF (флаг нуля), если EAX=0 Думайте сами, решайте сами... Помню, ещё в детстве очень хотел сделать так, чтобы свет в спальне можно было включать/выключать, не вставая с кровати ИЛИ(!) при входе в комнату. Большинство сразу же подумает: пультик - лучшее решение. А вот и нет! На самом деле при помощи логики можно обойтись без всяких сложных электронных наворотов простыми средствами. Давайте размышлять. Если подключить выключатели последовательно подобно схеме AND, то нужно будет включить оба выключателя, чтобы свет загорелся. Такое решение сделает неудобным процесс включения света. Если же подключить выключатели параллельно - как OR, то придётся выключать оба выключателя, чтобы свет погас. Соответственно, придётся прикладывать лишние усилия, чтобы выключать свет. Выходит, наша задача состоит в том, чтобы исключить недостатки и последовательной, и параллельной схемы. Или, выражаясь языком наполовину полного стакана, нужно объединить преимущества этих двух подключений. Создать некий промежуточный вариант. Параллельно-последовательное включение-выключение. К сожалению, сам я когда-то поленился придумать этот велосипед самостоятельно и теперь так никогда и не узнаю, сколько времени у меня ушло бы на изобретение (думать, что я бы так и недопёр, даже не хочется =). Завидую тем, кто ещё не знает решения. Очень рекомендую взять листок бумаги и рисовать, рисовать, рисовать до тех пор, пока не сможете найти простое красивое подключение. Пускай это займёт час, два и больше. Люди, которые допёрли самостоятельно, говорят, что удовольствие того стоит. ... На случай если за два часа ничего не вышло, открывайте первую подсказку. ПОДСКАЗКА №1: В схеме всего 2 переключаемых элемента. На следующий день дополнительные подсказки =). ПОДСКАЗКА №2: Это не совсем выключатели. ПОДСКАЗКА №3: Это два переключателя. У каждого переключателя только 2 состояния. Ну и исключительно, чтобы убедиться в правильности решения, ОТВЕТ: А теперь распишите, пожалуйста, таблицу всех возможных значений этой схемы нулями и единицами. Получилось? Отлично. Вспомним команду, при помощи которой мы шифровали строку в prax09 XOR - логическое побитовое, исключающее ИЛИ. Работает подобно OR, с одним лишь отличием: XOR выключает бит, если в обоих операндах он был включен. Мы уже рассматривали таблицу значений XOR в нулевом витке, но сейчас самое время повторить: 0101 XOR 1001 ---- 1100 Сравните таблицу значений XOR с таблицей параллельно-последовательной схемы, которую вы только что расписали. Заметили? Должно быть, оно же, но только с противоположным результатом. Для того чтобы параллельно-последовательная схема представляла логическое действие, исключающее ИЛИ, достаточно сделать простое допущение: лампочка горит = 0 лампочка погасла = 1 Но если во всей схеме процессора мы приняли положительную трактовку сигнала (лампочка горит = 1), то на практике этот фокус не прокатит. Придётся чуточку усовершенствовать саму схему с помощью следующего логического элемента... NOT – всё наоборот Самое очевидное действие – НЕ (в смысле отрицание). Операнд только один, а таблица значений состоит всего из двух возможных комбинаций: 01 NOT 10 Так и команда ассемблера NOT имеет только один операнд. В результате её действия значение каждого бита в операнде будет инвертировано. Фактически логика "НЕ" реализуется в обычном электромагнитном реле. Когда ток подаётся на катушку, контакты выключателя размыкаются, когда тока нет – контакты замыкаются. Понятно, что обычные выключатели, переключатели и реле в далёком прошлом. Современный техпроцесс позволяет разместить на кремниевых пластинках миллионы переключаемых элементов на каждый см2 и это только на один слой, а слоёв может быть больше, чем в моих любимых круасанах. В общих чертах базовую логику мы уже рассмотрели. Все вычисления (такие как сложение/вычитание, умножение/деление и дальше, вплоть до самых сложных математических действий) ЦП реализует путём комбинации всё тех же переключаемых элементов, то есть в основе лежат именно AND, OR, XOR и NOT. Честно признаюсь: сам я глубоко не вникал даже в принципиальную схему команды ADD, но в общих чертах каждому необходимо понимать, как на базе логических элементов выстроены сложные компоненты, присутствующие внутри микросхем. И здесь вам поможет одна замечательная классическая книга Эндрю Таненбаума "Архитектура Компьютера". В 2007 году вышло 5-е издание на русском (доступно в сети). Обязательно загляните в неё! Мне хватило беглого осмотра картинок из главы 3 "Цифровой логический уровень" =). А когда устанете читать про вентили, ловушки и прочую техническую хрень, вот вам онлайн-игруха под названием XOR: http://liszkay.hu/xor/ Цель: удалить все кубики, пробел переворачивает курсор... Впрочем, есть игрушка, в 100 раз прикольнее, и тема как раз наша: BloXORz Развлекайтесь =). Наигрались? Тогда отдохните и возвращайтесь сюда со свежими мозгами и глазами. Будем решать одну головоломку, куда как круче детских игрушек. Раз, раз, проверка Но перед этим проверим, насколько вы прониклись темой. Несколько элементарных вопросов, на которые каждый должен ответить относительно быстро: 1. Что изменит следующая команда? and EAX,EAX ОТВЕТ: Состояние битов регистра EAX не изменится, может измениться только регистр флагов. 2. Команда TEST (если забыли, см. описание в нулевом витке) по какой логике работает? ОТВЕТ: По логике команды AND, но результат вычислений мнимый, и опять же - изменяется только состояние регистра флагов. 3. Какая команда использовалась бы для выборочного включения флагов в регистре Eflags, если бы у него было имя обращения и можно было бы явным образом включать биты этого регистра? А выключать? ОТВЕТ: Для включения подойдёт or, а для выключения - and. 4. Теперь решим задачку особой сложности (только для высокопоставленных дипломатов bit-миссии). NOT – всё наоборот, а давайте сделаем "не всё наоборот". Задача: сделать выборочное битовое сито для NOT (битовую маску). То есть создать такой код, чтобы можно было инвертировать лишь определённую часть значения. Вход: EAX – значение, EDX – маска Выход: будут инвертированы только те биты EAX, которые были включены в EDX Ход решения: Итак, у нас на входе 2 операнда EAX и EDX, а на выходе один-единственный результат. Давайте попробуем составить таблицу преобразований битов: EAX 0101 EDX 1001 ---- Выход: 1100 Результат: ТЪфу, ты ж, блин! Опять XOR получился! xor EAX,EDX =))) Наблюдая за окружающими, Юнга заметил, что радость местным жителям приносит вовсе не прелесть острова. Оказалось, что все, кто остался, все, ставшие аборигенами, постоянно учатся. На острове исключительно в процессе обучения можно испытать невероятное чувство блаженства. Причём если от учёбы толку нет, если просветление мозгов вовремя не наступает, эйфория сменяется самой настоящей ломкой. В конце концов, Юнга поговорил об этом с Учителем. - Эта звезда, - Учитель указал рукой на небо, - этот пляж, - Учитель просеял песок сквозь пальцы... - Сам остров пронизан силой познания. Мы давно изучаем этот феномен. Биологи утверждают, что метаболизм мыслящих существ здесь временно меняется. Физики говорят про уникальное излучение, про эффект резонанса собственных колебаний песчинок и звезды... Хотя это всего лишь очередная теория. Так или иначе, здесь остаются только самые способные ученики. Правда, у них появляется новая проблема... Долгожданный новый prax Всё, хватит шуток, вот она - обещанная головоломка. Вопрос: как посчитать все включённые биты (то есть единички) в EAX? Поясню задачу, если вдруг непонятна суть. Рассмотрим для примера конкретное число - 270h, в двоичном виде будет: 1001110000 Здесь 4 единички. А теперь попросите свой компьютер сосчитать их. Задача, между прочим, - не просто забавная головоломка, но и практически полезная штука (для чего, расскажу в другой главе). Не даром инженеры Интел решили-таки добавить отдельную команду POPCNT для её решения, правда, эта команда пока что есть далеко не во всех процессорах (только с поддержкой нового набора инструкций SSE4.2). Но мы и сами не безрукие, найдём решение. Как обычно, единого правильного ответа нет, их целая куча, так что каждый может подобрать один из вариантов и найти в нём свои плюсы. Сегодня я расскажу вам об одном классическом методе. Он основан на двух китах: 1) правило "разделяй и властвуй". 2) комп – это сплошные переключатели. Долблю, как дятел, одно и то же, а что делать: нового ничего нет =). Итак, поехали. Пока просто наблюдайте за ходом мыслей и наслаждайтесь эстетикой решения. Согласно принципу №1, задачу надо разделить на такие мелкие кусочки, что каждый из них будет решаться тривиально. Вспомните "адскую" главу "Системы счисления, виток1". Решая третью задачу из prax14, мы рассматривали число 5678 как полином (многочлен) и, загнав его в глубокие скобки, привели равенство как раз к такому тривиальному действию. Сейчас будет нечто подобное, только с другого ракурса (без всяких формул). К примеру, возьмём число D23Fh, в бинарном виде оно достаточно разнообразно: 1101 0010 0011 1111 Задачу можно раздробить на набор одних и тех же постоянно повторяющихся действий. В некоторых случаях удобно было бы даже создать функцию, которая в ходе решения задачи многократно вызывает сама себя. ... Такой подход называется рекурсия. Рекурсивные действия хорошо воспринимаются в виде ветвистого графа (дерева): Каляка-маляка из детсада, а не граф! Почему? Да потому что в верхней строке число в двоичном представлении, а дальше идут десятичные вычисления. Извращение сплошное! Но зато воспринимается как дважды два четыре =), а не 1+1=10b... И всё-таки нельзя так. Давайте рассмотрим те же действия, но только в бинарном виде: Вот, так уже лучше. Что нам даёт такое дробление? Даёт элементарную операцию в каждом "кубике". В нашем случае эту операцию не стоит оформлять в виде отдельной функции и даже в цикл её закручивать неэффективно, потому что количество шагов ничтожно по меркам ЦП. Но всё равно в общем смысле дальнейшее решение считается рекурсивным. Выразим на Ассемблере такую элементарную операцию только для двух бит (одного верхнего "квадратика"): ;Вход: в EAX учитываются только два младших бита ;Выход: в EAX сумма единичных значений двух младших бит mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг. 1-й бит займёт позицию нулевого and EDX,1 ; накладываем маску на все биты, кроме младшего (выкл. всё, нулевой бит не трогать) and EAX,1 ; аналогично для другого регистра add EAX,EDX ; а теперь просто складываем бывший первый бит и нулевой Таким нехитрым способом мы имеем сумму одного из четырёх возможных вариантов: 1+1, или 1+0, или 0+1, или 0+0. Всё больше и больше я буду отсылать вас к полноценному справочнику команд Ассемблера. Вот и про shr (от англ. shift right) скажу лишь то, что она похожа на команду ror, с которой мы уже знакомы, только shr не прокручивает биты, а просто вытесняет вправо. Не сложно догадаться, что существует и обратная команда - shl, про которую тоже рекомендую читать в справочнике. Теперь давайте подумаем, а можно ли выполнить действие сложения одновременно для всех пар рядом стоящих бит в регистре EAX? Можно. Можно одновременно решить сразу всю верхнюю строку графа. Причём изменение в коде настолько мелкое, что даже удивляет простота решения: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг and EDX,01010101010101010101010101010101b ; в копии накладываем маску на все старшие биты в парах and EAX,01010101010101010101010101010101b ; аналогично для другого регистра add EAX,EDX ; а теперь точно так же складываем Последняя команда сложения в данном случае складывает все "бывшие старшие" и младшие биты во всех парах и на выходе у нас в регистре EAX находится 16 суммарных значений всех единичных бит по парам. Обычное сложение работает потому, что нам наверняка известно: в паре бит может быть максимум 1+1 единичек, и эти единички займут те же самые два бита в виде 10b. Значит, переноса битов в старшие разряды быть просто не может. К следующему шагу переходите после полного осмысления кода. Согласно графу на следующем этапе надо укрупнить суммы шестнадцати пар до сумм восьми тетрад. Опять вернёмся на уровень минимальной единицы, теперь уже одной тетрады: ;Вход: в EAX учитывается только младшая тетрада ;Выход: в EAX сумма единичных значений двух пар младшей тетрады mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,11b ; биты №0 и №1 не трогать, всё остальное выкл. and EAX,11b ; аналогично для другого регистра add EAX,EDX ; складываем бывшую первую пару и нулевую Вникли? Здорово, правда? Решение для целого регистра идёт уже по накатанной: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,00110011001100110011001100110011b ; накладываем маску на все старшие пары and EAX,00110011001100110011001100110011b ; аналогично для другого регистра add EAX,EDX ; складываем пары Теперь в регистре суммы по тетрадам. Следующие шаги (сумма всех тетрад до байта, сумма всех байт до слова и сумма слов) решаются аналогично. С этого места лучше начать кодировать и думать самостоятельно. Попробуйте довести обработку EAX до финального результата. Задача, кстати, не детская. Программистов высшей квалификации на собеседованиях в крупнейших корпорациях по всему миру часто просят решить этот или похожий пример. Далеко не каждый соискатель способен сознательно описать шаги рекурсивного решения. И не думайте, что я такой гениальный: изобрёл алгоритм. Мозгов Bitfry'я хватает только на то, чтобы найти решение в книге. В данном случае мне помогли mr.Гугел и книга Hacker's Delighit (Г. Уоррен "Алгоритмические трюки для программистов"). Надеюсь, мои труды по разжёвыванию этой задачи не прошли даром. Надеюсь, хотя бы единицы начинающих читателей теперь смогут суммировать единицы в EAX самостоятельно. На всякий случай, полный код решения (без какой-либо оптимизации) будет лежать в prax16. Очень надеюсь, что он вам не понадобится. А в следующей главе, наверное, будем писать первое окошко для Windows. Bitfry <<предыдущая глава следующая глава>> Вернуться на главную
логика меняется. Тут достаточно включить или "A", или "Б". Соответственно называется эта схема "ИЛИ".
На вопрос: "Кто больше нравится - брюнетки или блондинки?", настоящий мужчина всегда отвечает - "да".
Замените лампочку одним битом регистра, а выключатели - битами операндов, и перед вами окажется самая простая трактовка механизма работы двух основных логических команд Ассемблера:
Все 4 варианта переключения битов выглядят так:
0101 AND 1001 ---- Результат: 0001 0101 OR 1001 ---- Результат: 1101
Думаю, это несложно понять. Теперь осталось только закрепить на практике, разобрав несколько жизненных примеров.
Получаем из символьного кода цифры её значение (в prax14 делали так с одним байтом, теперь сразу 4):
mov EAX, 31323334h ; загружаем ASCII-коды символов "1234" and EAX, 0F0F0F0Fh ; в EAX будет 01020304h
Таким образом, мы "убиваем" старшую тетраду каждого байта и не изменяем младшую.
Разумеется, так же можно обнулять и E-часть регистра:
mov EAX, 12345678h ; загружаем любое число and EAX, 0000FFFFh ; в EAX будет 00005678h
И даже весь регистр:
and EAX, 0 ; в EAX будет 0
Можно сделать число чётным:
mov EAX, 77777777h ; загружаем любое число and EAX, -2 ; -2 это ведь 11111111 11111111 11111111 11111110b ; Теперь в EAX обязательно чётное число ("очётили" в младшую сторону)
Можно сделать число кратным степени двойки:
mov EAX, 77777777h ; загружаем любое число and EAX, -4 ; -4 это ведь 11111111 11111111 11111111 11111100b ; Теперь в EAX число, обязательно кратное 4 в младшую сторону and EAX, -10h ;-10h это ведь 11111111 11111111 11111111 11110000b ; А теперь обязательно кратное 16 в младшую сторону
Хорошо, а что может делать OR?
Например, в обратную сторону получаем символьный код цифры из значения:
mov EAX, 01020304h ; загружаем значения or EAX, 30303030h ; в EAX будут ASCII-коды символов "1234"
Таким образом, мы записываем в старшую тетраду каждого байта тройку и не изменяем младшую тетраду.
Соответственно, легко сделать число нечётным:
mov EAX, 88888888h ; загружаем некоторое число or EAX, 1 ; Теперь в EAX обязательно нечётное число ("онечётили" в большую сторону)
То есть можно включить любой нужный бит или сразу несколько битов:
or EAX, 10101010 10101010 10101010 10101010b
Обычно это делается для того, чтобы задавать параметры или состояния, которые предварительно описывают в константах, примерно так:
ICON_FLAG equ 1 ; 0001b OPEN_FLAG equ 2 ; 0010b EDIT_FLAG equ 4 ; 0100b X_FLAG equ 8 ; 1000b ... or dword ptr [Status], EDIT_FLAG ; вкл. состояние редактирования (бит № 2)
Бинарники любят спорить. Они спорят так часто, что уже давно знают результат любого спора. И всё равно они спорят. Спорят даже в тех случаях, когда результат не меняется. Впрочем, иногда цель спора не очевидна. Возможно, молодой бинат просто хочет произвести впечатление на красотку с флагом.
Чаще всего команду OR используют хитрее. Проверить регистр на ноль можно так:
or EAX,EAX ; не изменяет содержимое регистра, но включает ZF (флаг нуля), если EAX=0
Помню, ещё в детстве очень хотел сделать так, чтобы свет в спальне можно было включать/выключать, не вставая с кровати ИЛИ(!) при входе в комнату. Большинство сразу же подумает: пультик - лучшее решение. А вот и нет! На самом деле при помощи логики можно обойтись без всяких сложных электронных наворотов простыми средствами.
Давайте размышлять.
Если подключить выключатели последовательно подобно схеме AND, то нужно будет включить оба выключателя, чтобы свет загорелся. Такое решение сделает неудобным процесс включения света.
Если же подключить выключатели параллельно - как OR, то придётся выключать оба выключателя, чтобы свет погас. Соответственно, придётся прикладывать лишние усилия, чтобы выключать свет.
Выходит, наша задача состоит в том, чтобы исключить недостатки и последовательной, и параллельной схемы. Или, выражаясь языком наполовину полного стакана, нужно объединить преимущества этих двух подключений. Создать некий промежуточный вариант. Параллельно-последовательное включение-выключение.
К сожалению, сам я когда-то поленился придумать этот велосипед самостоятельно и теперь так никогда и не узнаю, сколько времени у меня ушло бы на изобретение (думать, что я бы так и недопёр, даже не хочется =). Завидую тем, кто ещё не знает решения. Очень рекомендую взять листок бумаги и рисовать, рисовать, рисовать до тех пор, пока не сможете найти простое красивое подключение. Пускай это займёт час, два и больше. Люди, которые допёрли самостоятельно, говорят, что удовольствие того стоит.
...
На случай если за два часа ничего не вышло, открывайте первую подсказку.
ПОДСКАЗКА №1:
На следующий день дополнительные подсказки =).
ПОДСКАЗКА №2:
ПОДСКАЗКА №3:
Ну и исключительно, чтобы убедиться в правильности решения,
ОТВЕТ:
А теперь распишите, пожалуйста, таблицу всех возможных значений этой схемы нулями и единицами.
Получилось?
Отлично.
Вспомним команду, при помощи которой мы шифровали строку в prax09
XOR - логическое побитовое, исключающее ИЛИ. Работает подобно OR, с одним лишь отличием: XOR выключает бит, если в обоих операндах он был включен.
Мы уже рассматривали таблицу значений XOR в нулевом витке, но сейчас самое время повторить:
0101 XOR 1001 ---- 1100
Сравните таблицу значений XOR с таблицей параллельно-последовательной схемы, которую вы только что расписали.
Заметили? Должно быть, оно же, но только с противоположным результатом.
Для того чтобы параллельно-последовательная схема представляла логическое действие, исключающее ИЛИ, достаточно сделать простое допущение:
лампочка горит = 0
лампочка погасла = 1
Но если во всей схеме процессора мы приняли положительную трактовку сигнала (лампочка горит = 1), то на практике этот фокус не прокатит. Придётся чуточку усовершенствовать саму схему с помощью следующего логического элемента...
Самое очевидное действие – НЕ (в смысле отрицание). Операнд только один, а таблица значений состоит всего из двух возможных комбинаций:
01 NOT 10
Так и команда ассемблера NOT имеет только один операнд. В результате её действия значение каждого бита в операнде будет инвертировано.
Фактически логика "НЕ" реализуется в обычном электромагнитном реле. Когда ток подаётся на катушку, контакты выключателя размыкаются, когда тока нет – контакты замыкаются.
Понятно, что обычные выключатели, переключатели и реле в далёком прошлом. Современный техпроцесс позволяет разместить на кремниевых пластинках миллионы переключаемых элементов на каждый см2 и это только на один слой, а слоёв может быть больше, чем в моих любимых круасанах.
В общих чертах базовую логику мы уже рассмотрели. Все вычисления (такие как сложение/вычитание, умножение/деление и дальше, вплоть до самых сложных математических действий) ЦП реализует путём комбинации всё тех же переключаемых элементов, то есть в основе лежат именно AND, OR, XOR и NOT. Честно признаюсь: сам я глубоко не вникал даже в принципиальную схему команды ADD, но в общих чертах каждому необходимо понимать, как на базе логических элементов выстроены сложные компоненты, присутствующие внутри микросхем. И здесь вам поможет одна замечательная классическая книга Эндрю Таненбаума "Архитектура Компьютера". В 2007 году вышло 5-е издание на русском (доступно в сети). Обязательно загляните в неё! Мне хватило беглого осмотра картинок из главы 3 "Цифровой логический уровень" =).
А когда устанете читать про вентили, ловушки и прочую техническую хрень, вот вам онлайн-игруха под названием XOR:
http://liszkay.hu/xor/
Цель: удалить все кубики, пробел переворачивает курсор...
Впрочем, есть игрушка, в 100 раз прикольнее, и тема как раз наша:
BloXORz
Развлекайтесь =).
Наигрались? Тогда отдохните и возвращайтесь сюда со свежими мозгами и глазами. Будем решать одну головоломку, куда как круче детских игрушек.
Но перед этим проверим, насколько вы прониклись темой.
Несколько элементарных вопросов, на которые каждый должен ответить относительно быстро:
1. Что изменит следующая команда?
and EAX,EAX
2. Команда TEST (если забыли, см. описание в нулевом витке) по какой логике работает?
3. Какая команда использовалась бы для выборочного включения флагов в регистре Eflags, если бы у него было имя обращения и можно было бы явным образом включать биты этого регистра? А выключать?
4. Теперь решим задачку особой сложности (только для высокопоставленных дипломатов bit-миссии).
NOT – всё наоборот, а давайте сделаем "не всё наоборот".
Задача: сделать выборочное битовое сито для NOT (битовую маску). То есть создать такой код, чтобы можно было инвертировать лишь определённую часть значения.
Вход: EAX – значение, EDX – маска
Выход: будут инвертированы только те биты EAX, которые были включены в EDX
Ход решения:
EAX 0101 EDX 1001 ---- Выход: 1100
Результат:
xor EAX,EDX =)))
Наблюдая за окружающими, Юнга заметил, что радость местным жителям приносит вовсе не прелесть острова. Оказалось, что все, кто остался, все, ставшие аборигенами, постоянно учатся. На острове исключительно в процессе обучения можно испытать невероятное чувство блаженства. Причём если от учёбы толку нет, если просветление мозгов вовремя не наступает, эйфория сменяется самой настоящей ломкой. В конце концов, Юнга поговорил об этом с Учителем.
- Эта звезда, - Учитель указал рукой на небо, - этот пляж, - Учитель просеял песок сквозь пальцы... - Сам остров пронизан силой познания. Мы давно изучаем этот феномен. Биологи утверждают, что метаболизм мыслящих существ здесь временно меняется. Физики говорят про уникальное излучение, про эффект резонанса собственных колебаний песчинок и звезды... Хотя это всего лишь очередная теория.
Так или иначе, здесь остаются только самые способные ученики. Правда, у них появляется новая проблема...
Всё, хватит шуток, вот она - обещанная головоломка.
Вопрос: как посчитать все включённые биты (то есть единички) в EAX?
Поясню задачу, если вдруг непонятна суть. Рассмотрим для примера конкретное число - 270h, в двоичном виде будет:
1001110000
Здесь 4 единички. А теперь попросите свой компьютер сосчитать их.
Задача, между прочим, - не просто забавная головоломка, но и практически полезная штука (для чего, расскажу в другой главе). Не даром инженеры Интел решили-таки добавить отдельную команду POPCNT для её решения, правда, эта команда пока что есть далеко не во всех процессорах (только с поддержкой нового набора инструкций SSE4.2).
Но мы и сами не безрукие, найдём решение.
Как обычно, единого правильного ответа нет, их целая куча, так что каждый может подобрать один из вариантов и найти в нём свои плюсы.
Сегодня я расскажу вам об одном классическом методе. Он основан на двух китах:
1) правило "разделяй и властвуй".
2) комп – это сплошные переключатели.
Долблю, как дятел, одно и то же, а что делать: нового ничего нет =).
Итак, поехали.
Пока просто наблюдайте за ходом мыслей и наслаждайтесь эстетикой решения.
Согласно принципу №1, задачу надо разделить на такие мелкие кусочки, что каждый из них будет решаться тривиально. Вспомните "адскую" главу "Системы счисления, виток1". Решая третью задачу из prax14, мы рассматривали число 5678 как полином (многочлен) и, загнав его в глубокие скобки, привели равенство как раз к такому тривиальному действию. Сейчас будет нечто подобное, только с другого ракурса (без всяких формул).
К примеру, возьмём число D23Fh, в бинарном виде оно достаточно разнообразно:
1101 0010 0011 1111
Задачу можно раздробить на набор одних и тех же постоянно повторяющихся действий. В некоторых случаях удобно было бы даже создать функцию, которая в ходе решения задачи многократно вызывает сама себя.
Такой подход называется рекурсия. Рекурсивные действия хорошо воспринимаются в виде ветвистого графа (дерева):
Каляка-маляка из детсада, а не граф! Почему? Да потому что в верхней строке число в двоичном представлении, а дальше идут десятичные вычисления. Извращение сплошное! Но зато воспринимается как дважды два четыре =), а не 1+1=10b... И всё-таки нельзя так. Давайте рассмотрим те же действия, но только в бинарном виде: Вот, так уже лучше. Что нам даёт такое дробление? Даёт элементарную операцию в каждом "кубике". В нашем случае эту операцию не стоит оформлять в виде отдельной функции и даже в цикл её закручивать неэффективно, потому что количество шагов ничтожно по меркам ЦП. Но всё равно в общем смысле дальнейшее решение считается рекурсивным. Выразим на Ассемблере такую элементарную операцию только для двух бит (одного верхнего "квадратика"): ;Вход: в EAX учитываются только два младших бита ;Выход: в EAX сумма единичных значений двух младших бит mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг. 1-й бит займёт позицию нулевого and EDX,1 ; накладываем маску на все биты, кроме младшего (выкл. всё, нулевой бит не трогать) and EAX,1 ; аналогично для другого регистра add EAX,EDX ; а теперь просто складываем бывший первый бит и нулевой Таким нехитрым способом мы имеем сумму одного из четырёх возможных вариантов: 1+1, или 1+0, или 0+1, или 0+0. Всё больше и больше я буду отсылать вас к полноценному справочнику команд Ассемблера. Вот и про shr (от англ. shift right) скажу лишь то, что она похожа на команду ror, с которой мы уже знакомы, только shr не прокручивает биты, а просто вытесняет вправо. Не сложно догадаться, что существует и обратная команда - shl, про которую тоже рекомендую читать в справочнике. Теперь давайте подумаем, а можно ли выполнить действие сложения одновременно для всех пар рядом стоящих бит в регистре EAX? Можно. Можно одновременно решить сразу всю верхнюю строку графа. Причём изменение в коде настолько мелкое, что даже удивляет простота решения: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг and EDX,01010101010101010101010101010101b ; в копии накладываем маску на все старшие биты в парах and EAX,01010101010101010101010101010101b ; аналогично для другого регистра add EAX,EDX ; а теперь точно так же складываем Последняя команда сложения в данном случае складывает все "бывшие старшие" и младшие биты во всех парах и на выходе у нас в регистре EAX находится 16 суммарных значений всех единичных бит по парам. Обычное сложение работает потому, что нам наверняка известно: в паре бит может быть максимум 1+1 единичек, и эти единички займут те же самые два бита в виде 10b. Значит, переноса битов в старшие разряды быть просто не может. К следующему шагу переходите после полного осмысления кода. Согласно графу на следующем этапе надо укрупнить суммы шестнадцати пар до сумм восьми тетрад. Опять вернёмся на уровень минимальной единицы, теперь уже одной тетрады: ;Вход: в EAX учитывается только младшая тетрада ;Выход: в EAX сумма единичных значений двух пар младшей тетрады mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,11b ; биты №0 и №1 не трогать, всё остальное выкл. and EAX,11b ; аналогично для другого регистра add EAX,EDX ; складываем бывшую первую пару и нулевую Вникли? Здорово, правда? Решение для целого регистра идёт уже по накатанной: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,00110011001100110011001100110011b ; накладываем маску на все старшие пары and EAX,00110011001100110011001100110011b ; аналогично для другого регистра add EAX,EDX ; складываем пары Теперь в регистре суммы по тетрадам. Следующие шаги (сумма всех тетрад до байта, сумма всех байт до слова и сумма слов) решаются аналогично. С этого места лучше начать кодировать и думать самостоятельно. Попробуйте довести обработку EAX до финального результата. Задача, кстати, не детская. Программистов высшей квалификации на собеседованиях в крупнейших корпорациях по всему миру часто просят решить этот или похожий пример. Далеко не каждый соискатель способен сознательно описать шаги рекурсивного решения. И не думайте, что я такой гениальный: изобрёл алгоритм. Мозгов Bitfry'я хватает только на то, чтобы найти решение в книге. В данном случае мне помогли mr.Гугел и книга Hacker's Delighit (Г. Уоррен "Алгоритмические трюки для программистов"). Надеюсь, мои труды по разжёвыванию этой задачи не прошли даром. Надеюсь, хотя бы единицы начинающих читателей теперь смогут суммировать единицы в EAX самостоятельно. На всякий случай, полный код решения (без какой-либо оптимизации) будет лежать в prax16. Очень надеюсь, что он вам не понадобится. А в следующей главе, наверное, будем писать первое окошко для Windows. Bitfry <<предыдущая глава следующая глава>> Вернуться на главную
Каляка-маляка из детсада, а не граф!
Почему?
Да потому что в верхней строке число в двоичном представлении, а дальше идут десятичные вычисления. Извращение сплошное! Но зато воспринимается как дважды два четыре =), а не 1+1=10b... И всё-таки нельзя так. Давайте рассмотрим те же действия, но только в бинарном виде:
Вот, так уже лучше. Что нам даёт такое дробление? Даёт элементарную операцию в каждом "кубике". В нашем случае эту операцию не стоит оформлять в виде отдельной функции и даже в цикл её закручивать неэффективно, потому что количество шагов ничтожно по меркам ЦП. Но всё равно в общем смысле дальнейшее решение считается рекурсивным. Выразим на Ассемблере такую элементарную операцию только для двух бит (одного верхнего "квадратика"): ;Вход: в EAX учитываются только два младших бита ;Выход: в EAX сумма единичных значений двух младших бит mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг. 1-й бит займёт позицию нулевого and EDX,1 ; накладываем маску на все биты, кроме младшего (выкл. всё, нулевой бит не трогать) and EAX,1 ; аналогично для другого регистра add EAX,EDX ; а теперь просто складываем бывший первый бит и нулевой Таким нехитрым способом мы имеем сумму одного из четырёх возможных вариантов: 1+1, или 1+0, или 0+1, или 0+0. Всё больше и больше я буду отсылать вас к полноценному справочнику команд Ассемблера. Вот и про shr (от англ. shift right) скажу лишь то, что она похожа на команду ror, с которой мы уже знакомы, только shr не прокручивает биты, а просто вытесняет вправо. Не сложно догадаться, что существует и обратная команда - shl, про которую тоже рекомендую читать в справочнике. Теперь давайте подумаем, а можно ли выполнить действие сложения одновременно для всех пар рядом стоящих бит в регистре EAX? Можно. Можно одновременно решить сразу всю верхнюю строку графа. Причём изменение в коде настолько мелкое, что даже удивляет простота решения: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг and EDX,01010101010101010101010101010101b ; в копии накладываем маску на все старшие биты в парах and EAX,01010101010101010101010101010101b ; аналогично для другого регистра add EAX,EDX ; а теперь точно так же складываем Последняя команда сложения в данном случае складывает все "бывшие старшие" и младшие биты во всех парах и на выходе у нас в регистре EAX находится 16 суммарных значений всех единичных бит по парам. Обычное сложение работает потому, что нам наверняка известно: в паре бит может быть максимум 1+1 единичек, и эти единички займут те же самые два бита в виде 10b. Значит, переноса битов в старшие разряды быть просто не может. К следующему шагу переходите после полного осмысления кода. Согласно графу на следующем этапе надо укрупнить суммы шестнадцати пар до сумм восьми тетрад. Опять вернёмся на уровень минимальной единицы, теперь уже одной тетрады: ;Вход: в EAX учитывается только младшая тетрада ;Выход: в EAX сумма единичных значений двух пар младшей тетрады mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,11b ; биты №0 и №1 не трогать, всё остальное выкл. and EAX,11b ; аналогично для другого регистра add EAX,EDX ; складываем бывшую первую пару и нулевую Вникли? Здорово, правда? Решение для целого регистра идёт уже по накатанной: mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,00110011001100110011001100110011b ; накладываем маску на все старшие пары and EAX,00110011001100110011001100110011b ; аналогично для другого регистра add EAX,EDX ; складываем пары Теперь в регистре суммы по тетрадам. Следующие шаги (сумма всех тетрад до байта, сумма всех байт до слова и сумма слов) решаются аналогично. С этого места лучше начать кодировать и думать самостоятельно. Попробуйте довести обработку EAX до финального результата. Задача, кстати, не детская. Программистов высшей квалификации на собеседованиях в крупнейших корпорациях по всему миру часто просят решить этот или похожий пример. Далеко не каждый соискатель способен сознательно описать шаги рекурсивного решения. И не думайте, что я такой гениальный: изобрёл алгоритм. Мозгов Bitfry'я хватает только на то, чтобы найти решение в книге. В данном случае мне помогли mr.Гугел и книга Hacker's Delighit (Г. Уоррен "Алгоритмические трюки для программистов"). Надеюсь, мои труды по разжёвыванию этой задачи не прошли даром. Надеюсь, хотя бы единицы начинающих читателей теперь смогут суммировать единицы в EAX самостоятельно. На всякий случай, полный код решения (без какой-либо оптимизации) будет лежать в prax16. Очень надеюсь, что он вам не понадобится. А в следующей главе, наверное, будем писать первое окошко для Windows. Bitfry <<предыдущая глава следующая глава>> Вернуться на главную
Вот, так уже лучше. Что нам даёт такое дробление?
Даёт элементарную операцию в каждом "кубике". В нашем случае эту операцию не стоит оформлять в виде отдельной функции и даже в цикл её закручивать неэффективно, потому что количество шагов ничтожно по меркам ЦП. Но всё равно в общем смысле дальнейшее решение считается рекурсивным.
Выразим на Ассемблере такую элементарную операцию только для двух бит (одного верхнего "квадратика"):
;Вход: в EAX учитываются только два младших бита ;Выход: в EAX сумма единичных значений двух младших бит mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг. 1-й бит займёт позицию нулевого and EDX,1 ; накладываем маску на все биты, кроме младшего (выкл. всё, нулевой бит не трогать) and EAX,1 ; аналогично для другого регистра add EAX,EDX ; а теперь просто складываем бывший первый бит и нулевой
Таким нехитрым способом мы имеем сумму одного из четырёх возможных вариантов: 1+1, или 1+0, или 0+1, или 0+0.
Всё больше и больше я буду отсылать вас к полноценному справочнику команд Ассемблера. Вот и про shr (от англ. shift right) скажу лишь то, что она похожа на команду ror, с которой мы уже знакомы, только shr не прокручивает биты, а просто вытесняет вправо. Не сложно догадаться, что существует и обратная команда - shl, про которую тоже рекомендую читать в справочнике.
Теперь давайте подумаем, а можно ли выполнить действие сложения одновременно для всех пар рядом стоящих бит в регистре EAX? Можно. Можно одновременно решить сразу всю верхнюю строку графа. Причём изменение в коде настолько мелкое, что даже удивляет простота решения:
mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,1 ; в копии смещаем все биты вправо на 1 шаг and EDX,01010101010101010101010101010101b ; в копии накладываем маску на все старшие биты в парах and EAX,01010101010101010101010101010101b ; аналогично для другого регистра add EAX,EDX ; а теперь точно так же складываем
Последняя команда сложения в данном случае складывает все "бывшие старшие" и младшие биты во всех парах и на выходе у нас в регистре EAX находится 16 суммарных значений всех единичных бит по парам. Обычное сложение работает потому, что нам наверняка известно: в паре бит может быть максимум 1+1 единичек, и эти единички займут те же самые два бита в виде 10b. Значит, переноса битов в старшие разряды быть просто не может.
К следующему шагу переходите после полного осмысления кода.
Согласно графу на следующем этапе надо укрупнить суммы шестнадцати пар до сумм восьми тетрад. Опять вернёмся на уровень минимальной единицы, теперь уже одной тетрады:
;Вход: в EAX учитывается только младшая тетрада ;Выход: в EAX сумма единичных значений двух пар младшей тетрады mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,11b ; биты №0 и №1 не трогать, всё остальное выкл. and EAX,11b ; аналогично для другого регистра add EAX,EDX ; складываем бывшую первую пару и нулевую
Вникли? Здорово, правда? Решение для целого регистра идёт уже по накатанной:
mov EDX,EAX ; делаем копию входного значения, чтобы потом сложить shr EDX,2 ; в копии смещаем все биты вправо на 2 шага and EDX,00110011001100110011001100110011b ; накладываем маску на все старшие пары and EAX,00110011001100110011001100110011b ; аналогично для другого регистра add EAX,EDX ; складываем пары
Теперь в регистре суммы по тетрадам. Следующие шаги (сумма всех тетрад до байта, сумма всех байт до слова и сумма слов) решаются аналогично.
С этого места лучше начать кодировать и думать самостоятельно. Попробуйте довести обработку EAX до финального результата. Задача, кстати, не детская.
Программистов высшей квалификации на собеседованиях в крупнейших корпорациях по всему миру часто просят решить этот или похожий пример. Далеко не каждый соискатель способен сознательно описать шаги рекурсивного решения. И не думайте, что я такой гениальный: изобрёл алгоритм. Мозгов Bitfry'я хватает только на то, чтобы найти решение в книге. В данном случае мне помогли mr.Гугел и книга Hacker's Delighit (Г. Уоррен "Алгоритмические трюки для программистов"). Надеюсь, мои труды по разжёвыванию этой задачи не прошли даром. Надеюсь, хотя бы единицы начинающих читателей теперь смогут суммировать единицы в EAX самостоятельно.
На всякий случай, полный код решения (без какой-либо оптимизации) будет лежать в prax16. Очень надеюсь, что он вам не понадобится.
А в следующей главе, наверное, будем писать первое окошко для Windows.
Bitfry