How to convert a decimal base (10) to a negabinary base (-2)?

algorithm base base-conversion
Jason picture Jason · Feb 17, 2012 · Viewed 11k times · Source

I want to write a program to convert from decimal to negabinary.

I cannot figure out how to convert from decimal to negabinary.

I have no idea about how to find the rule and how it works.

Example: 7(base10)-->11011(base-2)

I just know it is 7 = (-2)^0*1 + (-2)^1*1 + (-2)^2*0 + (-2)^3*1 + (-2)^4*1.

Answer

kennytm picture kennytm · Feb 17, 2012

The algorithm is described in http://en.wikipedia.org/wiki/Negative_base#Calculation. Basically, you just pick the remainder as the positive base case and make sure the remainder is nonnegative and minimal. 

 7 = -3*-2 + 1  (least significant digit)
-3 =  2*-2 + 1
 2 = -1*-2 + 0
-1 =  1*-2 + 1
 1 =  0*-2 + 1  (most significant digit)

Related questions

Fastest way to find the largest power of 10 smaller than x

Is there any fast way to find the largest power of 10 smaller than a given number? I'm using this algorithm, at the moment, but something inside myself dies anytime I see it: 10**( int( math.log10(x) ) ) # python pow( 10, (int) log10(…

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More