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

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
What does O(log n) mean exactly?

I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportionally...and the same goes for, …

Read More