Как думать о побитовых операциях с отрицательным числом Python?

Question

Мне довольно трудно думать о отрицательных числах Python (и Python3) с бесконечной точностью и побитовых операциях. Это не 32-битный или 64-битный. 1 слева можно представить как «бесконечно много». Это не очень определенно, поэтому трудно иногда думать о том, как это работает.

Кажется, что может работать так: всегда делайте это больше, например, если вы работаете с натуральными числами, которые имеет 67 битов, тогда просто подумайте об операциях с отрицательными числами как о 96-битных или 128-битных. Это правильный способ думать об этом? Есть ли в спецификациях что-то, что говорит о том, как это работает или о чем следует подумать? (например, внутренняя реализация учитывает только положительное целое число и отрицательные числа как «имеющие еще 1 бит влево»?)

Answer 1

Вы должны думать о них как о бесконечно большом количестве 1 бита. В абстрактном виде, двоичное дополнение двоичное представление имеет бесконечно много единиц; не то, чтобы больше 1 можно было добавлять по мере необходимости, но эти 1 с уже являются частью представления числа.

Тот факт, что эти бесконечно много битов на самом деле не хранятся в памяти, подробности реализации, поэтому, когда вы думаете об этом, вы должны игнорировать ограничения памяти, пока не окажетесь в ситуации, когда вы - это тот, кто должен написать реализацию. Если вы просто пытаетесь понять это концептуально, вам не нужно думать о таких вещах, как запасные биты, и я не думаю, что это обязательно поможет.

---

Двоичное число представляет собой сумму степени 2, например:

11001 ₂ = 2 ⁴ + 2 ³ + 0 + 0 + 2 ⁰

Число -1 представлено бесконечной последовательностью 1 с, простирающейся бесконечно далеко влево:

... 1111 ₂ = ... + 2 ³ + 2 ² + 2 ¹ + 2 ⁰

Это бессмыслица в обычном смысле бесконечного ряда, но есть веские причины определять результат как -1. Наиболее интуитивно привлекательной причиной является то, что происходит, когда вы добавляете 1 к нему, следуя алгоритму сложения:

  ...111111111
+            1
  ――――――――――――
= ...000000000 (result)
  ――――――――――――
  ...11111111  (carry)

В самом правом столбце у вас есть 1 + 1, который равен 2, или 10 ₂ в двоичном виде, поэтому вы пишете 0 и переносите 1 в следующий столбец слева. Затем в этом столбце у вас есть 1 плюс переносимая 1, поэтому вы пишете 0 и переносите еще 1 ... и т. Д., ad infinitum . Результат имеет 0 в каждой позиции. Следовательно, ... 11111 ₂ должно было представлять -1, потому что мы следовали алгоритму, чтобы добавить 1, и мы получили представление 0.

Если этого недостаточно, то есть другие причины того, что ... 11111 ₂ следует интерпретировать как представление -1:

• Бесконечная сумма 1 + 2 + 4 + 8 + ... является геометрия c серия; формула для ряда геометрии c с постоянным отношением r равна 1 / (1 - r). Эта формула применяется только когда -1
• Бесконечная сумма 1 + 2 + 4 + 8 + .. на самом деле действительно сходится к -1 в 2-adi c норма .
• Результат -1 также может быть получен с помощью других определений, включая Суммирование Эйлера и , как отмечено в Википедии , любой метод суммирования, который является стабильным и линейным , связывает эту сумму с результатом ∞ или -1.

Я упоминаю об этом также потому, что они подразумевают, что определенные свойства все еще сохраняются в арифметике; применение обычных алгоритмов сложения, вычитания и умножения «до бесконечности» дает ощутимые результаты, подчиняющиеся обычным свойствам арифметики c, таким как ассоциативность, коммутативность и дистрибутивность.

Answer 2

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

Я также не думаю, что вы не понимаете концепцию бесконечного числа 1 на слева. Положительное целое число: резервные несохраненные биты в 0, сохранение всех 1 битов с наименьшей значимостью Отрицательное целое число: резервные несохраненные биты в 1, сохранение всех 0 битов с наименьшей значимости

Когда необходимо выполнить побитовую операцию 2 с бесконечной точностью, вам нужно работать только с запасным битом. Пример:

-25 ^ -1029
-25 = -1 - 8 - 16: 11100(+infinitely many unsaved 1's beyond these 5 saved bits)
-1029 = -1 - 4 - 1024: 11011111110(+infinitely many unsaved 1's beyond these 11 saved bits)
Take XOR, you have to fill more 1's to align the longer one. So it is:
11100111111(+infinitely many unsaved 1's beyond this)
^
11011111110(+infinitely many unsaved 1's beyond this)
=
00111000001(+infinitely many unsaved 0's beyond this)
= 4 + 8 + 16 + 1024 = 1052

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