Побитовое умножение для достижения результата

Question

Существует ли общий набор правил для достижения определенного числа путем умножения известного и неизвестного числа. , например. Пусть х = 13 и г = 9

Есть ли способ, чтобы найти у таких, что

x * y = z  
=> 13 * y = 9 

Я не хочу, чтобы использовать их в качестве математических чисел, а с точки зрения битов. Итак, я хочу сохранить z int. Очевидно, что в представлении бит существует переполнение, но я не уверен, как найти z без грубой форсировки всех значений в 32-разрядной машине. Я думаю, у будет очень небольшое число, отрицательное.

Примечание: это не присвоение hw, поэтому вы можете изменить x и y на что угодно, это всего лишь примеры.

Answer 1

Во-первых, найдите modular multiplicative inverse от x (13) mod 2 . Есть несколько способов сделать это, многие люди рекомендуют расширенный алгоритм Евклида, но это не самый простой для этого случая. См. Главу 10 Хакерского восторга (целочисленное деление на константы) для более простого алгоритма.

Во всяком случае, если вы знаете, что модульный мультипликативный обратный 13 мод 2 является 0xc4ec4ec5, умножить это число на z, чтобы получить y.

0xc4ec4ec5 * 9 = 0xec4ec4ed

Так y = 0xec4ec4ed и 0xec4ec4ed * 13 действительно 9.

Обратите внимание, что если x даже, не имеет обратного. Если это «не более, чем z» (то есть оно имеет столько или меньше обратных нулей, что и z), вы можете решить его таким образом, разделив их максимальную общую мощность 2.