Two Complement's Python (with As Least Bits As Possible)

I am trying to output the binary representation of an negative number with the least bytes available each time. Example: -3 -> 101 -10 -> 10110

Solution 1:

Here's a way to do this using the .bit_length method of Python 3 integers. It also uses the string .format method to do the integer to binary string conversion. This function returns a string starting with '0' for non-negative numbers so that they can be distinguished from negative numbers.

deftwos_complement(n):
    m = n + 1if n < 0else n
    bitlen = 1 + m.bit_length()
    mask = (1 << bitlen) - 1return'{0:0{1}b}'.format(n & mask, bitlen)

for i in (-10, -3, 0, 3, 10):
    print('{:3}: {}'.format(i, twos_complement(i)))

print('- ' * 30)

for i inrange(-15, 16):
    print(i, twos_complement(i))    

output

-10: 10110
 -3: 101
  0: 0
  3: 011
 10: 01010
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -15 10001-14 10010-13 10011-12 10100-11 10101-10 10110-9 10111-8 1000-7 1001-6 1010-5 1011-4 100-3 101-2 10-1 1
0 0
1 01
2 010
3 011
4 0100
5 0101
6 0110
7 0111
8 01000
9 01001
10 01010
11 01011
12 01100
13 01101
14 01110
15 01111

---

How it works

Python uses a modified form of two's complement to represent integers. Python integers have no size limit, so negative integers behave as if they have an infinite number of leading 1 bits, as explained in the Python Wiki article on Bitwise Operators.

The int.bit_length method tells us the minimum number of bits required to represent a number, we want one more bit than that so that all our non-negative numbers will start with 0 and all the negative numbers start with a 1. We need to modify that slightly to ensure that numbers of the form -2**n will only get a single leading one bit, we do that by adding 1 to all the negative numbers when calculating the bit length.

To select the bits we want we need a bit mask of the appropriate length. If the bit length is 4, we want a mask of 1111 = 2**4 - 1; we _could calculate it by using exponentiation, but it's more efficient to use bit shifting: (1 << bitlen) - 1. We then do the bitwise AND operation n & mask to select the bits we want. Fortunately, Python gives us a non-negative number when we perform such masking operations. :)

Finally we convert the resulting integer to a string using the .format method. We use a nested format specification so we can dynamically specify the correct length of the output string. In

'{0:0{1}b}'.format(n & mask, bitlen) 

the first 0 of the format spec says that we're converting the value of the 0 arg in the argument list (n & mask), the :0{1}b says to convert it to binary, padded with leading zeroes if necessary, using the value of the 1 arg in the argument list (bitlen) as the total string length.

You can read about nested format specs in the Format String Syntax section of the docs:

A format_spec field can also include nested replacement fields within it. These nested replacement fields may contain a field name, conversion flag and format specification, but deeper nesting is not allowed. The replacement fields within the format_spec are substituted before the format_spec string is interpreted. This allows the formatting of a value to be dynamically specified.