How to think about Python's negative number bitwise operations?

user_12955159 0
Viewed 990

I find it quite difficult to think about Python (and Python3)'s infinite precision negative numbers and bitwise operations. It is not 32-bit or 64-bit. The 1s at the left can be thought of as "infinitely many". It is not very definite, which is why it is difficult to think about how it works sometimes.

It seems one way that might work is: always make it more, such as if you are dealing with positive integers that has 67 bits, then just think about the operations of them with the negative numbers as having 96-bit or 128-bit. Is this a correct way to think about it? Is there anything that is in the specs that says how it works or should be thought about? (such as the internal implementation just take the positive integer into consideration, and just take the negative numbers as "having 1 more bit to the left"?)

negative-number bit-manipulation python-3.x python
2 Answers

You should think of them as having infinitely many 1 bits. In the abstract, the two's complement binary representation has infinitely many 1s; not that more 1s can be added as necessary, but those 1s are already part of how the number is represented.

The fact that those infinitely many bits aren't actually stored in memory is an implementation detail, so when you're thinking about this you should ignore the limitations of memory until you are in a situation when you are the one who has to write the implementation. If you are just seeking to understand this conceptually, you don't need to think about things like fallback bits, and I don't think it necessarily helps to.

A binary number represents a sum of powers of 2, for example:

110012 = 24 + 23 + 0 + 0 + 20

The number -1 is represented by an infinite sequence of 1s, extending infinitely far left:

...11112 = ... + 23 + 22 + 21 + 20

This is nonsense in the usual sense of an infinite series, but there are good reasons to define the result as -1. The most intuitively appealing reason is what happens when you add 1 to it, by following the addition algorithm:

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

In the rightmost column you have 1 + 1 which is 2, or 102 in binary, so you write a 0 and carry a 1 to the next column left. Then in that column you have a 1 plus the carried 1, so you write 0 and carry another 1... and so on, ad infinitum. The result has a 0 in every position. Therefore, ...111112 must have represented -1 because we followed the algorithm to add 1, and we got a representation of 0.

If that's not satisfying enough, then there are other reasons that ...111112 ought to be interpreted as a representation of -1:

  • The infinite sum 1 + 2 + 4 + 8 + ... is a geometric series; the formula for a geometric series with constant ratio r is 1/(1 - r). This formula only applies when -1 < r < 1, but if we plug in r = 2 anyway, then we do get the result -1.
  • The infinite sum 1 + 2 + 4 + 8 + ... actually does converge to -1 in the 2-adic norm.
  • The result -1 can also be obtained by other definitions including Euler summation, and as noted by Wikipedia any summation method which is both stable and linear associates this sum either with the result ∞ or -1.

I mention these also because they imply that certain properties still hold about arithmetic; applying the usual algorithms for addition, subtraction and multiplication "out to infinity" give sensible results obeying the usual properties of arithmetic like associativity, commutativity and distributivity.

user_122990000

There are many ways to implement the infinite precision, but you should have raise your actual situation here to obtain the answer.

I also don't think you do not understand the concept of infinitely many 1's on the left. Positive Integer: fallback unsaved bits to 0, save all the 1 bits from least significance Negative Integer: fallback unsaved bits to 1, save all the 0 bits from least significance

When you need to perform bit-wise operation on 2 infinite precision ones, you only need to operate on the fallback bit as well. Example:

-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

From your question I don't think you really need the technical detail about how Python implement this...

user_130073810
Related