0
$\begingroup$

I have an homework question but I'm having hard time to understand the context. Here is the question:

  1. Assume that you are using 3-digit number system with base r = 4 (and n = 3). Assume also that you are using four’s complement scheme to represent signed integers and for subtraction operation.

a. Show the range of integers that can be represented 4s complement signed number system.

In the (a), I tried to use formula that I derived from 2's complement but it seems that somehow it's not correct. $$[-4^{n-1},4^{n-1}-1]$$

This formula gives [-16,15] but shouldn't the numbers whose leading digit is 0 and 1 be positive? That gives positive numbers from 0 to 31, but I don't know what to do with the negative ones.

$\endgroup$
  • $\begingroup$ Isn't this the whole idea of $n$'s complement scheme? $\endgroup$ – konewka Oct 16 '14 at 9:29
  • $\begingroup$ I am not sure what do you mean? $\endgroup$ – hevele Oct 16 '14 at 9:33
  • $\begingroup$ I'll explain it in an answer $\endgroup$ – konewka Oct 16 '14 at 9:35
1
$\begingroup$

Based on wiki's entry on Method of complements.

  • The radix complement of an n digit number $y$ in radix $b$ is $b^n-y$.
  • The diminished radix complement is $( b^n - 1 )-y$.
  • The two's complement refers to the radix complement of a number in base $2$.
  • The ones' complement refers to the diminished radix complement of a number in base $2$.
  • The four's complement refers to the radix complement of a number in base $4$.
  • The fours' complement refers to the diminished radix complement of a number in base $5$.

Assuming you have copied down the method of complements correctly and it is indeed four's complement we are talking about, a $n$-digit negative number $-x$ will be represented by the string corresponds to $4^n - x$. For example, the number $-1$ will be represented as a string with $n$ characters of '$3$'.

In general, the legal range for numbers will be $[-\frac{4^n}{2}, \frac{4^n}{2} - 1 ]$. In certain sense, working with numbers in four's complement is like working with ordinary integers under modulus arithmetic with modulus equal to $4^n$.

$\endgroup$
  • $\begingroup$ Thanks for your explanation. I came up with that already but there is something that I don't understand. If there are 31 positive numbers, they are the numbers whose MSB are 0 or 1, and the negative ones' MSB are 2 or 3, right?. I usually calculate 2's complements by taking the negative of MSB in binary form. So 111 = -2^2 + 2^1 + 2^0 = -1 in decimal. This one doesn't work on the numbers that start with 3 in 4's complement. 300 = -3*4^2 = -48, but it should be complement of 16. What's wrong with my logic? $\endgroup$ – hevele Oct 16 '14 at 10:46
  • $\begingroup$ @MertToka Yes, non-negative numbers are those whose MSB are either $0$ or $1$ and negative numbers are those with $2$ or $3$. For taking 4's complement, I don't understand what you are doing. This is what I will do: $$300_{4} \xrightarrow{\text{flip all bits}} 033_{4} \xrightarrow{+1} 100_{4} = 16_{10}$$. $\endgroup$ – achille hui Oct 16 '14 at 12:16
0
$\begingroup$

This is the idea of the $r$'s complement scheme.

Namely, say we have some base $r$ in which we have $n$-digit numbers. Normally these numbers would be identified with $[0,r^n-1]$, e.g. $r=2,n=4$ gives you numbers

0000 to 1111

which are (in base 10) equal to $[0,31]=[0,r^n-1]$.

But, when we use $r$'s complement scheme, the first digit of our number in base $r$ will indicate the sign of that number, e.g. again with $r=2, n=4$:

1010

will be equal to -1. This should explain your interval $[-16,15]$

$\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.