10 Dec 2014

Negabinary

Thought you knew all there is to know about number systems? Well, here's something new to that list - Negabinary numbers. These are numbers that are written to the base -2 (negative two). What's so great about these numbers? There is no need to put any + or - to denote whether it is a positive number or not. Let's check these numbers out.

The normal way a number is defined, works here as well. There are "b" number of digits in a number system of base "b". Here, we just have to change the definition to: there are "|b|" number of digits in a number system of base "b". The definition works perfectly after that. Then, we can just use the following equation:


Using this we can thus generate the first few numbers (0, 1, 2, 3, 4, 5...) in negabinary: 0, 1, 110, 111, 100, 101... (Sequence A039724 on Online Encyclopedia of Integer Sequences (OEIS)) where 0 and 1 have usual face values.

How do we convert a number to this base then? Write the number down in binary first. Then, going from right to left, at every odd place (i.e. x1, x3, x5 ...), if the bit is one, propagate a carry to the next bit. Also, while moving from right to left, add all the carries.

For example:

To convert 15 to negabinary:
  1. Convert 15 to binary
    • 15decimal=1111binary
  2. Propagate from right to left
    • 1111
    • 1111
    • 1211
    • 2011
    • 2011
    • 10011
    • 10011
    • 10011negabinary
  3. Done! (This is correct since 16-0+0-2+1 = 15)
Conversion to decimal (or any other base) just uses the original formula.

Addition is kinda done the way conversion is done, except that carries are propagated (one bit extra to the left, since 2negabinary = 110).

We can similarly define the other operations as well.

Let's take this onto another level itself: how about a number system that takes care of complex numbers as well (as digit strings)? I leave that upto you to figure out and comment about.

PS: This post is cross published on my blog http://jaybosamiya.blogspot.in/2014/10/negabinary.html

No comments:

Post a Comment