# Python convert int to binary efficiently

Below are several ways to convert an int to binary string.

```
# coding: utf-8
def f1(num):
if not num:
return '0'
bin_str = ''
while num:
bin_str = ('1' if (num & 1) else '0') + bin_str
num >>= 1
return bin_str
NUM_TO_BIN_0XFF = dict((i, bin(i)[2:]) for i in range(0xFF + 1))
def f2(num):
if not num:
return '0'
bin_str = ''
while num:
bin_str = NUM_TO_BIN_0XFF[num & 0xFF] + bin_str
num >>= 8
return bin_str
NUM_TO_BIN_0XFFFF = dict((i, bin(i)[2:]) for i in range(0xFFFF + 1))
def f3(num):
if not num:
return '0'
bin_str = ''
while num:
bin_str = NUM_TO_BIN_0XFFFF[num & 0xFFFF] + bin_str
num >>= 16
return bin_str
NUMS = list(range(0xFFFF + 1))
if __name__ == '__main__':
from timeit import Timer
number = 10
timer = Timer('for i in NUMS: bin(i)', 'from __main__ import f1, NUMS')
print(int(timer.timeit(number=number) / number / len(NUMS) * 1e9))
timer = Timer('for i in NUMS: bin(i)[2:]', 'from __main__ import f1, NUMS')
print(int(timer.timeit(number=number) / number / len(NUMS) * 1e9))
timer = Timer('for i in NUMS: \'{0:b}\'.format(i)', 'from __main__ import f1, NUMS')
print(int(timer.timeit(number=number) / number / len(NUMS) * 1e9))
timer = Timer('for i in NUMS: f1(i)', 'from __main__ import f1, NUMS')
print(int(timer.timeit(number=number) / number / len(NUMS) * 1e9))
timer = Timer('for i in NUMS: f2(i)', 'from __main__ import f2, NUMS')
print(int(timer.timeit(number=number) / number / len(NUMS) * 1e9))
timer = Timer('for i in NUMS: f3(i)', 'from __main__ import f3, NUMS')
print(int(timer.timeit(number=number) / number / len(NUMS) * 1e9))
```

`f1`

checks the rightmost bit of the number and then right-shifts the number by one bit.

`f2`

uses a pre-computed dict to map the rightmost byte of the number to binary string and then right-shifts the number by 8 bits.

`f3`

uses a pre-computed dict to map the rightmost two bytes of the number to binary string and then right-shifts the number by 16 bits.

The benchmarking result on my computer is:

`bin(i)[2:]`

: 1.59x of`bin(i)`

.`'{0:b}'.format(i)`

: 2.36x of`bin(i)`

.`f1(i)`

: 25.36x of`bin(i)`

.`f2(i)`

: 4.42x of`bin(i)`

.`f3(i)`

: 2.86x of`bin(i)`

.

We can see `bin`

is the fastest. `f1`

is very slow. The pre-computing approach of `f2`

and `f3`

makes their performance not an order of magnitude slower than the built-in `bin`

function.

Now let's take a look of the source code of the built-in `bin`

function to see why it is fast.

Here is the definition of `bin`

. It in turn calls PyNumber_ToBase, which in turn calls _PyLong_Format, which in turn calls long_format_binary.

As shown here, an int object is internally represented as an array of `digit`

(i.e. `uint32_t`

). Each `digit`

stores 30 bits of the int. This explains the way the number of bits of an int is computed in `long_format_binary`

at here. Notice the last `digit`

's number of bits is computed using `bits_in_digit`

, to exclude leading zeros.

At here, a unicode object is created.

At here, macro WRITE_UNICODE_DIGITS is called to write the unicode object's internal data. At here, a pointer to the internal data is obtained. Notice the `+ sz`

part, it means to write the internal data from end to start.

At here, macro WRITE_DIGITS is called.

At here, each `digit`

's bits are put in `accum`

. The `<< accumbits`

part puts the bits in higher location in case there are some leftover bits from the previous `digit`

. Leftover bits may appear because at here `bits`

bits are handled each time and at here if there are less than `bits`

in `accum`

, the do-while loop will stop (unless it is handling the last `digit`

), the next `digit`

's bits will be added to `accum`

. The value of `bits`

is 1 for base 2, 3 for base 8, and 4 for base 16. So for base 2, leftover bits will not appear.

At here, the `bits`

bits are mapped to the corresponding digit of the target base.

At here, the digit is written to the unicode internal data.

At here, the number of bits in `accum`

is reduced.

At here, `accum`

is right-shifted to discard the bits already handled.

That's how the built-in `bin`

function implements the int-to-binary conversion. In summary, it is fast because:

- 1. It is implemented in C.
- 2. It can access the internal bits of an int object. The mapping from each group of bits to a digit of the target base is implemented by a simple
`char`

offset. - 3. The digits of the target base are directly written to the unicode object's internal data.

Comments: