Ресурс (ы) для обучения побитовой операции?

Question

Мне недавно задали вопрос, "how do you multiply without using the multiplication operator, without any sort of looping statements or explicit addition", и я понял, что совсем не знаком с побитовой операцией.

Очевидно, что Википедия , но мне нужно кое-что с более подробным объяснением, ориентированным на новичка. Есть также руководство по взлому , но я еще не дошел до его понимания.

Я не против, если вы укажете главу в книге, поскольку у меня есть доступ к хорошей библиотеке через Safari Books и другие ресурсы.

Answer 1

Кнут , том 2 - Полу численные алгоритмы

Answer 2

Суть этого сводится к «половинному сумматору» и «полному сумматору».Половина сумматора добавляет два бита ввода для получения однобитного результата и однобитного переноса.Полный сумматор добавляет три бита ввода (два нормальных входа плюс перенос из младшего бита) для получения однобитного результата и переноса в один бит.

В любом случае результат основан наТаблица правды для сложения.Для половины сумматора, то есть: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 + перенос.

Итак, «нормальная» часть результатаXOR входов.«Несущая» часть результата - это «И» входов. Полный сумматор почти такой же, но оставлен как печально известное «упражнение для читателя».

Собирая их вместе, вы используете половину-адреса для младшего значащего бита и полные сумматоры для других битов, чтобы добавить N входных битов.

Как только вы можете сделать сложение, есть несколько способов сделать умножение. Простой (и медленный)способ умножения NxM состоит в добавлении N к себе M раз. Более быстрый (но несколько более сложный для понимания) способ состоит в сдвиге и сложении. Например, Nx5 = Nx4 + Nx1. Вы можете создать NxB, где B = 2 ^L , сдвигая N влево на L бит.