Base 4 Mathematics

Question

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

3. 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.

Answer 1

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]$

Answer 2

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