Обратное умножение в 64-битной арифметике

Я пытаюсь выполнить умножение и деление с 64-битными целыми числами. Я хочу, чтобы мои результаты были 64-битными, любое переполнение должно быть усечено. Мне удалось заставить его работать с умножениями:

z = 0xed5c6911
y = 0xFFFFFFFF & (z * 33)

print hex(z)
print hex(y)

Это выводит:

0xed5c6911
0x98e98b31

как и ожидалось.

Я хотел бы изменить это сейчас:

z = 0xFFFFFFFF & (y / 33)
print hex(z)

Я ожидал бы 0xed5c6911, исходное значение z, но я получаю 0x4a23a85.

Как я могу отменить операцию, выполненную в первом фрагменте, и получить исходное значение z из y?


python multiplication integer 64-bit division
person Juicy    schedule 20.09.2015    source источник

Ответы (3)


arrow_upward
4
arrow_downward

обновление: после комментария гарольда: ваша маска только 32-битная - чтобы замаскировать 64-битную нужно замаскировать все ваши целые числа с помощью & 0xFFFFFFFFFFFFFFFF.

все, что следует ниже, относится к 32-разрядной версии:

можно выполнить обратную операцию: усекая до 32 бит, вы эффективно выполняете вычисления в кольце целых чисел Z/2^32 Z. 33 есть модульный обратный мультипликатив:

1/33 = 0x3e0f83e1  mod  2^32

поэтому для любого 32-битного числа вы можете обратить умножение на 33, умножив его на число, указанное выше (и усекая до 32-бит).

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

обратите внимание, что только нечетные числа в этом кольце имеют обратное (2 - единственный простой делитель 2 ^ 32).

для 64 бит значение, обратное 33:

1/33 = 0x0f83e0f83e0f83e1  mod  2^64
person hiro protagonist    schedule 20.09.2015
comment
Простите мое невежество, но я не уверен, как это интерпретировать. Как я могу реализовать это на Python? - person Juicy; 20.09.2015
comment
Конечно! псевдокод в википедии близок к python; в противном случае попробуйте это: stackoverflow.com/questions/12519535/ - person hiro protagonist; 20.09.2015
comment
А разве это не Z/2^32Z? Из-за маскировки? - person harold; 21.09.2015
comment
ты прав! эта FF последовательность казалась ужасно короткой! ой. я должен проверить ваш блог! - person hiro protagonist; 21.09.2015

arrow_upward
0
arrow_downward

Эта операция необратима. Когда вы умножаете z на 33, вы выталкиваете самый верхний 64-й бит за пределы 64-битного предела и уничтожаете информацию из-за переполнения.

Вы можете увидеть значение 0xed5c6911 в двоичном формате с помощью Google.

Другими словами, для выполнения этой операции необходимо использовать тип данных шире 64 бит. Например, вы можете использовать long:

z = long(0xed5c6911)
y = long(0xFFFFFFFFFFFF) & (z * 33) # Note the added F's
print hex(z)  # 0xed5c6911L
print hex(y)  # 0x1e98e98b31L

Используя long, вы можете отменить эту операцию:

z = 0xFFFFFFFFFFFF & (y / 33) # Again, note the added F's
print hex(z) # 0xed5c6911L
person Alex    schedule 20.09.2015
comment
При умножении на 33 (или любое другое нечетное число) информация не теряется; см. ответ @hiro-protagonist. - person Don Hatch; 24.07.2019

arrow_upward
-2
arrow_downward

Вы не сможете получить исходное значение z из y.

Когда вы усекаете умножение (z * 33) в своем первом примере, вы теряете информацию — в данном случае старшие биты. Затем, когда вы выполняете деление, вы делите другое значение, чем (z * 33), и поэтому не сможете восстановить z.

Чтобы действительно вернуть z, вам нужно сохранить некоторую дополнительную информацию — самый простой способ — использовать тип данных с большим количеством битов.

person Andrew Huang    schedule 20.09.2015
comment
При умножении на 33 (или любое другое нечетное число) информация не теряется; см. ответ @hiro-protagonist. - person Don Hatch; 24.07.2019