pythonbinarybitcomplementones-complement

Confusion with 1's compliment binary representation


I was trying to learn binary representation of negative numbers. I tried to output 12 and ~12 in binary.

print(~12)

Output:

-13

This was the 1's complement of 12.

But my doubt is that binary 12 is 1100 and -13 (1's complement of 12) is 0011 but 3 is also 0011 in binary. This was very confusing for me.

How -13 and 3 can have same binary values?


Solution

  • TLDR: -13 and 3 do not have the same binary values. The confusion arises from ignoring explicit sign and padding/width.


    Python integers behave as unsigned arbitrary width binary numbers, with a separate sign bit. There is no general, unambiguous binary representation for signed numbers.

    For example, 12 is the number ...1100 and the sign +, and -12 is the same number ...1100 but the sign -. Notably, the ... may be arbitrary many leading digits – 1100, 01100, 001100 and so on are all the same number. This 0-padding allows to treat small and large numbers alike, e.g. the at-least 4-digit 12 ...1100 can be aligned with the at-least 5-digit 16 ...10000.

    This means there cannot be a specific leading sign bit, since each position could be preceded by another 0. Instead, the sign bit arbitrarily precedes the number: 0...1100 or +...1100 is 12, and 1...1100 or -...1100 is -12. This is visible in the canonical bitwise representation of numbers separating the sign and absolute value.

    >>> bin(12)
    0b1100
    >>> bin(-12)
    -0b1100
    

    As such, the 4-digit bitwise complement of 12 is -0011, while 3 is +0011.