1
$\begingroup$

Using $n$-bit integers we can usually represent anything from $0$ to $2^n-1$. If we're interpreting a number with $2$'s complement, then the first bit is the sign bit, and we represent $-x$ with $2^n-x$. So for example, normally:

$n=4$:

\begin{array}{|c|c|} \hline \text{Decimal} & \text{Binary}\\ \hline 0 & 0000 \\ \hline 1 & 0001 \\ \hline 2 & 0010 \\ \hline 3 & 0011 \\ \hline 4 & 0100 \\ \hline 5 & 0101 \\ \hline 6 & 0110 \\ \hline 7 & 0111 \\ \hline 8 & 1000 \\ \hline 9 & 1001 \\ \hline 10 & 1010 \\ \hline 11 & 1011 \\ \hline 12 & 1100 \\ \hline 13 & 1101 \\ \hline 14 & 1110 \\ \hline 15 & 1111 \\ \hline \end{array}

But using $2$'s complement:

\begin{array}{|c|c|} \hline \text{Decimal} & \text{Binary}\\ \hline 0 & 0000 \\ \hline 1 & 0001 \\ \hline 2 & 0010 \\ \hline 3 & 0011 \\ \hline 4 & 0100 \\ \hline 5 & 0101 \\ \hline 6 & 0110 \\ \hline 7 & 0111 \\ \hline -8 & 1000 \\ \hline -7 & 1001 \\ \hline -6 & 1010 \\ \hline -5 & 1011 \\ \hline -4 & 1100 \\ \hline -3 & 1101 \\ \hline -2 & 1110 \\ \hline -1 & 1111 \\ \hline \end{array}

Now apparently if we add two numbers using $2$'s complement we still get the right answer even if we have to truncate the leftmost bit, and this is bending my brain at the moment.

If I have two negative numbers $-x$ and $-y$, then adding them gives us $2^{n+1} - (x + y)$ which after truncating gives us $-(x+y)$.

If I have a positive number $x$ and a negative number $-y$, then adding them gives us $x + (2^n - y) = 2^n - (-x + y)$ which is the representation for $-(-x+y)$ or $x-y$.

If I have a negative number $-x$ and a positive number $y$ then adding them gives us $2^n-x + y = 2^n-(x-y)$ which is the representation for $-(x-y)$ or $y-x$.

If I have two positive numbers $x$ and $y$ then adding them gives us $x+y$.

My question:

Looking at the four cases mentioned earlier, do we normally have to handle them separately, or is it really just doing arithmetic mod $2^n$ and everything will just work itself out naturally as long as everything ($x$, $y$, as well as $x+y$) is confined to $-2^{n-1}$ through $2^{n-1}-1$? For example using $4$ bits we could not be able to represent $(-8) + (-7) = -15$ since the sum falls outside the scope?

$\endgroup$
2
$\begingroup$

It's the latter – arithmetic mod $2^n$ and everything works itself out naturally. And yes, we can't represent $-15$ with $4$ bits because it's outside the scope.

$\endgroup$

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.