Introduction

Suppose we have a binary fraction, that is positive and less than 1:

0.101011000... = 0.671875
  | | ||
  | | |+-- 1/2^6
  | | +--- 1/2^5
  | +----- 1/2^3
  +------- 1/2^1

We want to express it as a ratio of two integer numbers.

Algorithm

The value of the sample number is:

 1      1      1      1
---- + ---- + ---- + ----
  1      3      5      6
 2      2      2      2

We want to add these fractions, and to do this we have to find the common denominator. In our case it will be the product of all denominators we have:

2¹ ⋅ 2³ ⋅ 2⁵ ⋅ 2⁶ = 2^{1 + 3 + 5 + 6} = 2¹⁵

Note that the exponent is simply sum of positions (counted from 1) of bits equal 1.

The numerator has the sum of four products; each product contains all but single power:

(2³ ⋅ 2⁵ ⋅ 2⁶) + (2¹ ⋅ 2⁵ ⋅ 2⁶) + (2¹ ⋅ 2³ ⋅ 2⁶) + (2¹ ⋅ 2³ ⋅ 2⁵)

It is simpler to express products using the denominator's power:

2^{15 − 1} + 2^{15 − 3} + 2^{15 − 5} + 2^{15 − 6} = 2¹⁴ + 2¹² + 2¹⁰ + 2⁹

Finally, we need to reduce the fraction. To do this, we simply find the minimum exponent from the numerator (it is 9) and subtract it from all powers of two present in the fraction. Thus finally we have:

(2^{14 − 9} + 2^{12 − 9} + 2^{10 − 9} + 2^{9 − 9})/2^{15 − 9} =

(2⁵ + 2³ + 2¹ + 2⁰)/2⁶ =

(32 + 8 + 2 + 1)/64 =

(32 + 8 + 2 + 1)/64 = 43/64 = 0.671875

The algorithm uses only simple arithmetic and bit operations.

Sample code

Sample source code is available on Github.