2

Bitwise not (~) is well-defined in languages that define a specific bit length and format for ints. Since in Python 3, ints can be any length, they by definition have variable number of bits. Internally, I believe Python uses at least 28 bytes to store an int, but of course these aren't what bitwise not is defined on.

How does Python define bitwise not:

  1. Is the bit length a function of the int size, the native platform, or something else?
  2. Does Python sign extend, zero extend, or do something else?
SRobertJames
  • 8,210
  • 14
  • 60
  • 107
  • 1
    As an aside, python doesn't define what `~` is, objects define that by how they implement the `__invert__` magic method. Tim Peters has the detailed information (not suprising there!). The implementation is at `https://github.com/python/cpython/blob/main/Objects/longobject.c`. And its comment is `/* Implement ~x as -(x+1) */`. – tdelaney Nov 24 '21 at 18:58
  • 1
    @tdelaney, true in general, but Python-the-language does define what `int.__invert__` does for the built-in `int` type. – Tim Peters Nov 24 '21 at 19:00
  • @TimPeters - I guess that depends on what "Python-the-language" means. The python compiler and byte code don't do anything special for invert. Its just a call to `__invert__`. And that's the case for all of the operators. That's Python-the-language to me and its central to the idea that everything's an object. There are no fundamental types that are implemented directly in the language. There are a bunch of builtin types that come with the language, but that's a different thing. (That's my 2 cents) – tdelaney Nov 24 '21 at 19:20
  • Python-the-language is defined by "The Python Language Reference" manual. All implementations claiming to be "Python" must implement integers as defined in the "Data model" chapter of that. "These represent numbers in an unlimited range, subject to available (virtual) memory only. For the purpose of shift and mask operations, a binary representation is assumed, and negative numbers are represented in a variant of 2’s complement which gives the illusion of an infinite string of sign bits extending to the left." – Tim Peters Nov 24 '21 at 19:27

1 Answers1

3

Python integers emulate 2's-complement represenation with "an infinite" number of sign bits (all 0 bits for >= 0, all 1 bits for < 0).

All bitwise integer operations maintain this useful illusion.

For example, 0 is an infinite number of 0 bits, and ~0 is an infinite number of 1 bits - which is -1 in 2's-complement notation.

>>> ~0
-1

It's generally true that ~i = -i-1, which, in English, can be read as "the 1's-complement of i is the 2's-complement of i minus 1".

For right shifts of integers, Python fills with more copies of the sign bit.

Tim Peters
  • 67,464
  • 13
  • 126
  • 132
  • I understand "infinite string of bits", but what does it mean "infinite string of _sign_ bits"? By definition, in two's complement, -1 will have all bits set, -2 will have all but one set, etc.; there is no dedicated "sign bit". – SRobertJames Nov 25 '21 at 05:59
  • In any fixed-width 2's complement integer type, "the sign bit" is the most-significant bit. The MSB is 1 if and only if the integer is negative. Unbounded Python ints are similarly negative if and only if they have a (conceptual) infinite string of 1 bits extending to the left (and non-negative if and only if an infinite string of 0 bits). From the Wikipedia article on "two's complement": "The most significant bit determines the sign of the number and is sometimes called the sign bit." It's standard usage of the phrase, although I agree potentially confusing. – Tim Peters Nov 25 '21 at 06:12