Decimal to Binary based on the logic B[i]*(2)^i Where i=[0,2,3...N-1]

Question

I have a function that takes a binary array and returns a decimal based on the below logic:

1  |  -2  |  4  |  -8  |  16  |  -32 ...
1  |  0   |  0  |  1   |  1   |  1   = 1 + 0 + 0 + (-8) + 16 + (-32) = -23

def bin_to_dec(bin_array):
    dec = 0
    for i in range(0, len(bin_array)):
        if i%2 == 0:
            dec += bin_array[i] * 2**i
        else:
            dec += bin_array[i] * -2**i
    print(dec)
    return dec

I am struggling with writing the decimal to binary piece of the above logic. As in a function that takes for example -23 as input, and returns [1,0,0,1,1,1]. Any help would be highly appreciated.

Answer 1

You can use a few observations to solve this:

1. Consider a 5-bit number with the coefficient of 16 as 1. What could be the maximum value of the number? 21 = 1 + 4 + 16. Similarly, minimum value would be 6 = 16 - 2 - 8. So, for any number between [6,21], the coefficient of 16 is guaranteed to be 1.
2. Similarly, for a 6 bit number, if -32's bit is 1, the range of numbers will be between [-42, 11] -32 - 2 - 8 = -42 and -32 + 16 + 4 + 1 = 11
3. Now, each number x can be expressed in two ways for our problem:
   a. (some binary number <= x) + (some positive value) (for example, 20 = 16+4)
   b. (some binary number >= x) + (some negative value) (for example, 7 = 16+(-9))
4. Combining point #3 and #4, you can determine the most significant bit of the number. Calculate the range for the biggest binary number <= x (by binary number, I mean exponent of 2). If x is outside the upper limit of the range, we'll use method 3b to express it as a sum, or else method 3a.
   Example: for 20, biggest exponent = 16 which has range [6,21], so we'll use 3a. However, for 30, we'll have to use 3b and express it as 64 + (some negative value).
5. Similarly, for negative numbers, you can use the lower bound of range to see which will be the biggest negative exponent. Example: for -9, biggest exponent = -8, which has range [-10,-3]. Since lower bound of -10 < -9, we can express it as -8 + (some negative value). For -14, we'll have to express it as -32 + (some positive value)

Using all of this, you can come with an implementation (either recursive or iterative, your decision). The algorithm would broadly look like:

convert(i):
x = rightmost bit/exponent for i
diff = difference between x and i
return x + convert(diff)

Using -23 as example:

1. Biggest exponenent <= -23 = -8. Since it is outside -8's range, we make it -32 + (9). Recursively solve for 9.
2. Biggest exponenent <= 9 = 4. Since it is outside 4's range, we make it 16 + (-7). Recursively solve for 7.
3. Biggest exponenent <= -7 = -2. Since it is outside -2's range, we make it -8 + (1). Recursively solve for 1.
4. For 1, we get 1.

So we get (-32)+(16)+(-8)+(1), which was the original summation.