20 March 2010

Weird binary!!

I read about weird binary at Varun Kumar's blog (http://varunkumar-n.blogspot.com/2010/03/weird-binary.html)

Number system with base as –2 (minus two) is commonly referred to as “Weird Binary”. Like binary number system, weird binary also uses the binary symbols 0, 1. The bit positions in weird binary represent the powers of (-2). For example: 11001 in weird binary represents 9 in decimal system. Weird binary
This number system reminds me a saying in Tamil regarding tough situations, "For every foot of climbing, Slipping 2 feet". ஜான் ஏறுனா மொழம் சறுக்குது .

So How to convert from decimal to weird-binary(base minus 2)?

But I didn't want to check-out others solutions to the problem, before trying it myself. I wanted to find a pen and paper way to calculate it, similar to the one we use to convert from decimal to binary. And found it interesting!

Just at every alternate step, instead of going for the maximum multiple of 2 less than previous balance, find the minimum multiple of 2, greater than previous balance.
IOW, at alternate steps, if the remainder was 1, add 1 to next balance(quotient).

Weird-binary can be used to represent negative numbers without any special sign-bit. But I still couldn't think of any use for this negative two base system. Can you? Is it being used anywhere?


Varun said...

Awesome!! I worked it out in the similar way.. but, was not able to reason out and structure properly.. U did it.. :-)

Think the odd positions increment can be related to the carry explained in the solution -- http://everything2.com/title/Base+minus+2+solution

Nikanth Karthikesan said...

The explanation is, that at each step we are actually dividing by -2, but divide in such a way that we get 1 or 0 as remainder, not -1 or 0 or 1

15 / -2 = -7 rem 1 [-2*-7+1=15]

-7 / -2 = 4 rem 1 [-2*4+1=-7]

4 / -2 = -2 rem 0 [-2*-2+0=4]

-2 / -2 = 1 rem 0 [-2*1+0=-2]

1 / -2 = 0 rem 1 [-2*0+1=1]

Gopal Kasturi said...

Excellent solution!