Сдвиг для умножения на любое число

Question

Используя только сложение, вычитание и сдвиг битов, как я могу умножить целое число на данное число?

Например, я хочу умножить целое число на 17.

Я знаю, чтосдвиг влево умножается на кратное 2, а сдвиг вправо делится на степень 2, но я не знаю, как это обобщить.

---

А как насчет отрицательных чисел?Преобразовать в дополнение к двум и выполнить ту же процедуру?

( РЕДАКТИРОВАТЬ: ОК, я понял, неважно.справа вместо права налево.)

---

Теперь начинается сложная часть. Мы можем использовать только 3 оператора.

Например, умножение на 60 Iможно выполнить с помощью этого:

(x << 5) + (x << 4) + (x << 3) + (x << 2)

Где x - это число, которое я умножаю.Но это 7 операторов - как я могу сжать это, чтобы использовать только 3?

Answer 1

Это называется сдвигом и сложением.В Википедии есть хорошее объяснение этого:

http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

РЕДАКТИРОВАТЬ: Чтобы ответить на ваш другой вопрос, да, преобразование в комплимент двух будет работать.Но вы должны подписать продлить его достаточно долго, чтобы вместить весь продукт.(при условии, что вы этого хотите)

РЕДАКТИРОВАТЬ 2: Если оба операнда отрицательны, просто комплимент двух с самого начала, и вам не придется об этом беспокоиться.

Answer 2

Вот пример умножения на 3:

unsigned int y = (x << 1) + (x << 0);

(где я предполагаю, что x также unsigned).

Надеюсь, вы сможете обобщить это.

Answer 3

17 = 16 + 1 = (2 ^ 4) + (2 ^ 0).Поэтому сдвиньте свое число влево на 4 бита (умножьте на 2 ^ 4 = 16) и добавьте к нему исходное число.

Другой способ посмотреть на это: 17 - это двоичное число 10001 (основание 2)так что вам нужна операция сдвига для каждого из битов, установленных в множителе (то есть биты 4 и 0, как указано выше).

Я не знаю C, поэтому я не буду смущать себя, предлагая код.

Answer 4

Насколько я знаю, в общем случае не существует простого способа умножения с использованием всего 3 операторов.

Возможно умножение на 60, поскольку 60 = 64 - 4: (x << 6) - (x << 2)