Playing with binary numbers (number system with base as 2) is always fun. But, what about playing with weird binary? What is it? 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 is little tough to understand and the operations with them will be complex unlike binary numbers. One of the most commonly asked interview question related to this is the conversion of decimal to weird binary. This problem originally appeared on an ACM contest. I came up with my solution on paper but it wasn’t structured. On further surfing, found out this solution with amazing explanation. But, I could not really understand what does this base (-2) mean and signify. Does it have any significance? Any help on understanding the same would be appreciated.
Update: Check out this interesting solution from Nikanth (@nikanth).
-- Varun
That's nuthin', check out Quater-imaginary base:
ReplyDeletehttp://en.wikipedia.org/wiki/Quater-imaginary_base
It was quiet interesting to solve!
ReplyDeletehttp://nikanth.blogspot.com/2010/03/weird-binary.html
p(n) = n to base 2, if n is an odd power of 2
ReplyDeletep(n) = p(n|n-1 + 1) - n, i.e p(next power of 2) - n if n is even power of 2
Assumming we know p(n) for all powers of 2 using the above method,
we can find p(n) for rest of the nos as follows
p(n) = p(2^a1) + p(2^a2) +.... p(2^ak)
where addition is binary
and n = 2^a1+2^a2+2^a3 +... +2^ak
a1 being the largest power of 2 that divides n
a2 being the largest power of 2 that divides n/2^a1
so on
-Manish Mulani
Manish,
ReplyDeleteLooks like p(n) calculation for powers of 2 should be reverse.
p(n) = n to base 2 if n is even right? Are you talking about addition (2) or (-2)?
It would be great if you work out an example.
--Varun