PDA

View Full Version : Implementing a Negabinary data type



pianorain
12-20-2004, 10:36 AM
I saw a discussion about the negabinary system here (http://cboard.cprogramming.com/showthread.php?t=51084&page=3&p=423189) and thought it might be fun to try to implement a data type that used it. I've run into a problem where math and my machine disagree.

According to Wikipedia (http://en.wikipedia.org/wiki/Negabinary), you should be able to convert a number from base 10 to base -2 by repeated divisions of -2. The problem I'm having is when I have -1 / -2. The integer-division part of my brain wants that to be 0, and so does my machine. However, the website claims that -1 / -2 = 1 with a remainder of 1, since if a / b = c with a remainder d, then bc + d = a.

Doing it their way, -2 * 1 + 1 = 1 -> 1 = 1.
Doing it the machine's way, -2 * 0 + -1 = -1 -> -1 = -1.

Is there some rule that you can't have a negative remainder?