3
$\begingroup$

A negabinary is a number with a base as -2. I want to add two such numbers. I know how to convert them into the corresponding decimal numbers but wanted to add them right away without conversion to decimal system.

For eg, if two numbers are 1011 and 1110, the output is 110001 in the negabinary addition. I understand the concept of a signed bit but could not comprehend this.

$\endgroup$
9
$\begingroup$

You add them just like regular binary numbers, except the carry is negative and should be subtracted from each column instead of added to it. $$ \begin{align} 1\color{red}1\phantom{1}\color{red}1\phantom{11}&\\ 1011&\\ {}+1110&\\ \hline =110001& \end{align} $$ (I'm using the color red to signify a carry with a negative value.) For that last $\color{red}1$, note that translates to $1$ with a positive (black) carry of $1$ (as $-1$ in regular numbers is $11$ in negabinary).

For a more convoluted example, consider $$ \begin{align} 1\color{red}11\color{red}1\phantom{0000}&\\ 101010&\\ {}+101100&\\ \hline =11110110\end{align} $$ The two lone negative $1$'s each give a result of $1$ in their respective columns, and a positive (black) carry of $1$. The column where you now have three (black) $1$'s gives (as "normal") a result of $1$ and a negative (red) carry to the next column. And this ought to address anything that can possibly happen in a column when adding two numbers together.

In the case that we have four $1$'s in one column, we have 0 for that column and 1 for the two consecutive columns (as 4 in decimal is equivalent to 100 in negabinary). Here is an example: $$ \begin{align} &\\ 00101 (+5)&\\ {}+00111 (+3)&\\ \hline =11000 (+8)\end{align} $$

$\endgroup$
11
  • $\begingroup$ These seem to be different negabinary to these: wolframalpha.com/input/?i=negabinary+6 $\endgroup$ – samerivertwice Jun 5 '19 at 8:32
  • 1
    $\begingroup$ No, it's exactly the same. The numbers you have here are $-9$ and $-6$, and they add to $-15$. All is well. (WolframAlpha is a bit wonky; if I ask it to convert $-6$ to negabinary, it will give me the exact same result as for $6$. That doesn't seem right.) $\endgroup$ – Arthur Jun 5 '19 at 8:53
  • 1
    $\begingroup$ @user334732 I get the same result as you do for $101010+101100$. Carries behave a bit weirdly, but one can get used to it. As for the representation of $6$, I get that to be $11010$ (just guessing: $16-8 -2$, but also attainable by adding $101+1$). So I have no idea what WA is doing. $\endgroup$ – Arthur Jun 5 '19 at 10:36
  • 1
    $\begingroup$ When you end up carrying a negative $1$ into an empty column you can either write $11$ immediately or you can write $1$ and carry a positive $1$ which then goes immediately in the result. The final result is the same either way. I see that at the moment you have shown one technique in one example and the other in the other example. $\endgroup$ – David K Jun 5 '19 at 11:17
  • 1
    $\begingroup$ @DavidK You're right. I fixed it so that it's more consistent, using the more careful strategy in both cases. $\endgroup$ – Arthur Jun 5 '19 at 11:31
2
$\begingroup$

There's a good rule for negabinary addition, which is really easy to use, and comprises a set of three cases which account for all eventualities, and is "sign-transitive" in the sense that you can apply it in any position, be it a negative or positive place-value:

$1+1=110$

$1+1+1=111$

$1+11=0$

(I'm assuming $1+0=1$ is obvious)

I was trying to remember where I saw this but it's 8 minutes into this which contains some other valuable insights.

$\endgroup$
2
  • $\begingroup$ @Arthur ^^ also useful. $\endgroup$ – samerivertwice Jun 6 '19 at 14:21
  • 1
    $\begingroup$ Thank you so much @user3344732 $\endgroup$ – Aviral Srivastava Jun 6 '19 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.