Chapter 12. Unusual Bases for Number Systems
This section discusses a few unusual positional number systems. They are just interesting curiosities and are probably not practical for anything. We limit the discussion to integers, but they can all be extended to include digits after the radix point—which usually, but not always, denotes non-integers.
12–1 Base –2
By using –2 as the base, both positive and negative integers can be expressed without an explicit sign or other irregularity, such as having a negative weight for the most significant bit (Knu3). The digits used are 0 and 1, as in base +2; that is, the value represented by a string of 1’s and 0’s is understood to be
(an...a3a2a1a0) = an(–2)n + ... + a3(–2)3 + a2(–2)2 + a1(–2) + a0.
From this, it can be seen that a procedure for finding the base −2, or “negabinary,” representation of an integer is to successively divide the number by −2, recording the remainders. The division must be such that it always gives a remainder of 0 or 1 (the digits to be used); that is, it must be modulus division. As an example, the plan below shows how to find the base −2 representation of –3.
Because we have reached a 0 quotient, the process terminates (if continued, the remaining quotients and remainders would all be 0). Thus, reading the remainders upward, we see that –3 is written 1101 in base –2.
Table 12–1 shows, on the left, how each bit pattern from 0000 to 1111 is interpreted in base –2, and on the right, how integers in the range –15 to +15 are represented.
TABLE 12–1. CONVERSIONS BETWEEN DECIMAL AND BASE–2
It is not obvious that the 2n possible bit patterns in an n-bit word uniquely represent all integers in a certain range, but this can be shown by induction. The inductive hypothesis is that an n-bit word represents all integers in the range
Assume first that n is even. For n = 2, the representable integers are 10, 11, 00, and 01 in base –2, or
–2, –1, 0, 1.
This agrees with (1a), and each integer in the range is represented once and only once.
A word of n + 1 bits can, with a leading bit of 0, represent all the integers given by (1a). In addition, with a leading bit of 1, it can represent all these integers biased by (–2)n = 2n. The new range is
2n − (2n + 1 – 2) / 3 to 2n + (2n– 1)/3,
(2n−1)/3 + 1 to (2n +2 − 1)/3.
This is contiguous to the range given by (1a), so for a word size of n + 1 bits, all integers in the range
−(2n + 1 − 2)/3 to (2n + 2 − 1)/3
are represented once and only once. This agrees with (1b), with n replaced by n + 1.
The proof that (1a) follows from (1b), for n odd, and that all integers in the range are uniquely represented, is similar.
To add and subtract, the usual rules, such as 0 + 1 = 1 and 1 – 1 = 0, of course apply. Because 2 is written 110, and –1 is written 11, and so on, the following additional rules apply. These, together with the obvious ones, suffice.
When adding or subtracting, there are sometimes two carry bits. The carry bits are to be added to their column, even when subtracting. It is convenient to place them both over the next bit to the left and simplify (when possible) using 11 + 1 = 0. If 11 is carried to a column that contains two 0’s, bring down a 1 and carry a 1. Below are examples.
Addition Subtraction
11 1 11 11 1 11 1 1
1 0 1 1 1 19 1 0 1 0 1 21
+ 1 1 0 1 0 1 +(-11) -1 0 1 1 1 0 -(-38)
----------------- ------ ---------------- -----
0 1 1 0 0 0 8 1 0 0 1 1 1 1 59
The only carries possible are 0, 1, and 11. Overflow occurs if there is a carry (either 1 or 11) out of the high-order position. These remarks apply to both addition and subtraction.
Because there are three possibilities for the carry, a base –2 adder would be more complex than a two’s-complement adder.
There are two ways to negate an integer. It can be added to itself shifted left one position (that is, multiply by –1), or it can be subtracted from 0. There is no rule as simple and convenient as the “complement and add 1” rule of two’s-complement arithmetic. In two’s-complement, this rule is used to build a subtracter from an adder (to compute A – B, form 
).
For base –2, there is no device quite that simple, but a method that is nearly as simple is to complement the minuend (meaning to invert each bit), add the complemented minuend to the subtrahend, and then complement the sum [Lang]. Here is an example showing the subtraction of 13 from 6 using this scheme on an eight-bit machine.
00011010 6
00011101 13
11100101 6 complemented
--------
11110110 (6 complemented) + 13
00001001 Complement of the sum (-7)
This method is using
A − B = I − ((I−A)+B)
in base –2 arithmetic, with I a word of all 1’s.
Multiplication of base –2 integers is straightforward. Just use the rule that 1 × 1 = 1 and 0 times either 0 or 1 is 0, and add the columns using base –2 addition.
Division, however, is quite complicated. It is a real challenge to devise a reasonable hardware division algorithm—that is, one based on repeated subtraction and shifting. Figure 12–1 shows an algorithm that is expressed, for definiteness, for an 8-bit machine. It does modulus division (nonnegative remainder).
Although this program is written in C and was tested on a binary two’s-complement machine, that is immaterial—it should be viewed somewhat abstractly. The input quantities n and d, and all internal variables except for q, are simply numbers without any particular representation. The output q is a string of bits to be interpreted in base –2.
This requires a little explanation. If the input quantities were in base –2, the algorithm would be very awkward to express in an executable form. For example, the test “if (d > 0)” would have to test that the most significant bit of d is in an even position. The addition in “c = c + d” would have to be a base –2 addition. The code would be very hard to read. The way the algorithm is coded, you should think of n and d as numbers without any particular representation. The code shows the arithmetic operations to be performed, whatever encoding is used. If the numbers are encoded in base –2, as they would be in hardware that implements this algorithm, the multiplication by –128 is a left shift of seven positions, and the divisions by –2 are right shifts of one position.
As examples, the code computes values as follows:
divbm2(6, 2) = 7 (six divided by two is 111–2)
divbm2(– 4, 3) = 2 (minus four divided by three is 10–2)
divbm2(–4, –3) = 6 (minus four divided by minus 3 is 110–2)
int divbm2(int n, int d) { // q = n/d in base -2.
int r, dw, c, q, i;
r = n; // Init. remainder.
dw = (-128)*d; // Position d.
c = (-43)*d; // Init. comparand.
if (d > 0) c = c + d;
q = 0; // Init. quotient.
for (i = 7; i >= 0; i--) {
if (d > 0 ^ (i&1) == 0 ^ r >= c {
q = q | (1 << i); // Set a quotient bit.
r = r - dw; // Subtract d shifted.
}
dw = dw/(-2); // Position d.
if (d > 0) c = c -2*d; // Set comparand for
else c = c + d; // next iteration.
c = c/(-2);
}
return q; // Return quotient in
// base -2.
// Remainder is r,
} // 0 <= r < |d|.
FIGURE 12-1. Division in base –2.
The step q = q | (1 << i); represents simply setting bit i of q. The next line—r = r - dw—represents reducing the remainder by the divisor d shifted left.
The algorithm is difficult to describe in detail, but we will try to give the general idea.
Consider determining the value of the first bit of the quotient, bit 7 of q. In base −2, 8-bit numbers that have their most significant bit “on” range in value from −170 to −43. Therefore, ignoring the possibility of overflow, the first (most significant) quotient bit will be 1 if (and only if) the quotient will be algebraically less than or equal to –43.
Because n = qd + r and for a positive divisor r ≤ d − 1, for a positive divisor the first quotient bit will be 1 iff n ≤ − 43d + (d − 1), or n < − 43d + d. For a negative divisor, the first quotient bit will be 1 iff n ≥ −43d (r ≥ 0 for modulus division).
Thus, the first quotient bit is 1 iff
(d > 0 & ¬(n ≥ −43d + d)) | (d < 0 & n ≥ −43d).
Ignoring the possibility that d = 0, this can be written as
d>0 ⊕ n ≥ c,
where c = −43d + d if d ≥ 0, and c = −43d if d < 0.
This is the logic for determining a quotient bit for an odd-numbered bit position. For an even-numbered position, the logic is reversed. Hence, the test includes the term (i&1) == 0. (The ^ character in the program denotes exclusive or.)
At each iteration, c is set equal to the smallest (closest to zero) integer that must have a 1-bit at position i after dividing by d. If the current remainder r exceeds that, then bit i of q is set to 1 and r is adjusted by subtracting the value of a 1 at that position, multiplied by the divisor d. No real multiplication is required here; d is simply positioned properly and subtracted.
The algorithm is not elegant. It is awkward to implement because there are several additions, subtractions, and comparisons, and there is even a multiplication (by a constant) that must be done at the beginning. One might hope for a “uniform” algorithm—one that does not test the signs of the arguments and do different things depending on the outcome. Such a uniform algorithm, however, probably does not exist for base –2 (or for two’s-complement arithmetic). The reason for this is that division is inherently a non-uniform process. Consider the simplest algorithm of the shift-and-subtract type. This algorithm would not shift at all, but for positive arguments would simply subtract the divisor from the dividend repeatedly, counting the number of subtractions performed until the remainder is less than the divisor. On the other hand, if the dividend is negative (and the divisor is positive), the process is to add the divisor repeatedly until the remainder is 0 or positive, and the quotient is the negative of the count obtained. The process is still different if the divisor is negative.
In spite of this, division is a uniform process for the signed-magnitude representation of numbers. With such a representation, the magnitudes are positive, so the algorithm can simply subtract magnitudes and count until the remainder is negative, and then set the sign bit of the quotient to the exclusive or of the arguments, and the sign bit of the remainder equal to the sign of the dividend (this gives ordinary truncating division).
The algorithm given above could be made more uniform, in a sense, by first complementing the divisor, if it is negative, and then performing the steps given as simplified by having d > 0. Then a correction would be performed at the end. For modulus division, the correction is to negate the quotient and leave the remainder unchanged. This moves some of the tests out of the loop, but the algorithm as a whole is still not pretty.
It is interesting to contrast the commonly used number representations and base –2 regarding the question of whether or not the computer hardware treats numbers uniformly in carrying out the four fundamental arithmetic operations. We don’t have a precise definition of “uniformly,” but basically it means free of operations that might or might not be done, depending on the signs of the arguments. We consider setting the sign bit of the result equal to the exclusive or of the signs of the arguments to be a uniform operation. Table 12–2 shows which operations treat their operands uniformly with various number representations.
One’s-complement addition and subtraction are done uniformly by means of the “end around carry” trick. For addition, all bits, including the sign bit, are added in the usual binary way, and the carry out of the leftmost bit (the sign bit) is added to the least significant position. This process always terminates right away (that is, the addition of the carry cannot generate another carry out of the sign bit position).
TABLE 12–2. UNIFORM OPERATIONS IN VARIOUS NUMBER ENCODINGS
In the case of two’s-complement multiplication, the entry is “yes” if only the right half of the doubleword product is desired.
We conclude this discussion of the base –2 number system with some observations about how to convert between straight binary and base –2.
To convert to binary from base –2, form a word that has only the bits with positive weight, and subtract a word that has only the bits with negative weight, using the subtraction rules of binary arithmetic. An alternative method that may be a little simpler is to extract the bits appearing in the negative weight positions, shift them one position to the left, and subtract the extracted number from the original number using the subtraction rules of ordinary binary arithmetic.
To convert to base –2 from binary, extract the bits appearing in the odd positions (positions weighted by 2n with n odd), shift them one position to the left, and add the two numbers using the addition rules of base –2. Here are two examples:
On a computer, with its fixed word size, these conversions work for negative numbers if the carries out of the high-order position are simply discarded. To illustrate, the example on the right above can be regarded as converting −9 to base −2 from binary if the word size is six bits.
The above algorithm for converting to base −2 cannot easily be implemented in software on a binary computer, because it requires doing addition in base −2. Schroeppel [HAK, item 128] overcomes this with a much more clever and useful way to do the conversions in both directions. To convert to binary, his method is
B ← (N ⊕ 0b10... 1010) − 0b10 ... 1010.
To see why this works, let the base –2 number consist of the four digits abcd. Then, interpreted (erroneously) in straight binary, this is 8a + 4b + 2 c + d. After the exclusive or, interpreted in binary it is 8(1 − a) + 4b + 2(1 − c) + d. After the (binary) subtraction of 8 + 2, it is − 8 a + 4b − 2 c + d, which is its value interpreted in base –2.
Schroeppel’s formula can be readily solved for N in terms of B, so it gives a three-instruction method for converting in the other direction. Collecting these results, we have the following formulas for converting to binary for a 32-bit machine:
B ← (N & 0x55555555) − (N & ¬0x55555555),
B ← N − ((N& 0xAAAAAAAA) << 1),
B ← (N ⊕ 0xAAAAAAAA) − 0xAAAAAAAA,
and the following, for converting to base –2 from binary:
N ← (B + 0xAAAAAAAA) ⊕ 0xAAAAAAAA.
12-2 Base –1 + i
By using – 1 + i as the base, where i is 
, all complex integers (complex numbers with integral real and imaginary parts) can be expressed as a single “number” without an explicit sign or other irregularity. Surprisingly, this can be done using only 0 and 1 for digits, and all integers are represented uniquely. We will not prove this or much else about this number system, but will just describe it very briefly.
It is not entirely trivial to discover how to write the integer 2.1 But it can be determined algorithmically by successively dividing 2 by the base and recording the remainders. What does a “remainder” mean in this context? We want the remainder after dividing by – 1 + i to be 0 or 1, if possible (so that the digits will be 0 or 1). To see that it is always possible, assume that we are to divide an arbitrary complex integer a + bi by − 1 + i. Then, we wish to find q and r such that q is a complex integer, r = 0 or 1, and
a + bi = (qr + qii)(− 1 + i)+r,
where qr and qt denote the real and imaginary parts of q, respectively. Equating real and imaginary parts and solving the two simultaneous equations for q gives
Clearly, if a and b are both even or are both odd, then by choosing r = 0, q is a complex integer. Furthermore, if one of a and b is even and the other is odd, then by choosing r = 1, q is a complex integer.
Thus, the integer 2 can be converted to base – 1 + i by the plan illustrated below.
Because the real and imaginary parts of the integer 2 are both even, we simply do the division, knowing that the remainder will be 0:
Because the real and imaginary parts of – 1 – i are both odd, again we simply divide, knowing that the remainder is 0:
Because the real and imaginary parts of i are even and odd, respectively, the remainder will be 1. It is simplest to account for this at the beginning by subtracting 1 from the dividend.
Because the real and imaginary parts of 1 are odd and even, the next remainder will be 1. Subtracting this from the dividend gives
Because we have reached a 0 quotient, the process terminates, and the base – 1 + i representation for 2 is seen to be 1100 (reading the remainders upward).
Table 12–3 shows how each bit pattern from 0000 to 1111 is interpreted in base – 1 + i and how the real integers in the range –15 to +15 are represented.
The addition rules for base – 1 + i (in addition to the trivial ones involving a 0-bit) are as follows:
TABLE 12–3. CONVERSIONS BETWEEN DECIMAL AND BASE –1 + i
When adding two numbers, the largest number of carries that occurs in one column is six, so the largest sum of a column is 8 (111000000). This makes for a rather complicated adder. If one were to build a complex arithmetic machine, it would no doubt be best to keep the real and imaginary parts separate,2 with each represented in some sensible way such as two’s-complement.
12–3 Other Bases
The base – 1 – i has essentially the same properties as the base – 1 + i discussed above. If a certain bit pattern represents the number a + bi in one of these bases, then the same bit pattern represents the number a – bi in the other base.
The bases 1 + i and 1 – i can also represent all the complex integers, using only 0 and 1 for digits. These two bases have the same complex-conjugate relationship to each other, as do the bases – 1 ± i. In bases 1 ± i, the representation of some integers has an infinite string of 1’s on the left, similar to the two’s-complement representation of negative integers. This arises naturally by using uniform rules for addition and subtraction, as in the case of two’s-complement. One such integer is 2, which (in either base) is written ...11101100. Thus, these bases have the rather complex addition rule 1 + 1 = ...11101100.
By grouping into pairs the bits in the base –2 representation of an integer, one obtains a base 4 representation for the positive and negative numbers, using the digits –2, –1, 0, and 1. For example,
−14decimal = 110110−2 = (−1)(1)(−2)4 = −1 · 42 + 1 · −41 −2 · 40
Similarly, by grouping into pairs the bits in the base – 1 + i representation of a complex integer, we obtain a base –2i representation for the complex integers using the digits 0, 1, – 1 + i, and i. This is a bit too complicated to be interesting.
The “quater-imaginary” system (Knu2) is similar. It represents the complex integers using 2i as a base, and the digits 0, 1, 2, and 3 (with no sign). To represent some integers, namely those with an odd imaginary component, it is necessary to use a digit to the right of the radix point. For example, i is written 10.2 in base 2i.
12–4 What Is the Most Efficient Base?
Suppose you are building a computer and you are trying to decide what base to use to represent integers. For the registers you have available circuits that are 2-state (binary), 3-state, 4-state, and so on. Which should you use?
Let us assume that the cost of a b-state circuit is proportional to b. Thus, a 3-state circuit costs 50% more than a binary circuit, a 4-state circuit costs twice as much as a binary circuit, and so on.
Suppose you want the registers to be able to hold integers from 0 to some maximum M. Encoding integers from 0 to M in base b requires ⌈logb(M + 1)⌉ digits (e.g., to represent all integers from 0 to 999,999 in decimal requires log10(1,000,000) = 6 digits).
One would expect the cost of a register to be equal to the product of the number of digits required times the cost to represent each digit:
c = klogb(M + 1) · b,
where c is the cost of a register and k is a constant of proportionality. For a given M, we wish to find b that minimizes the cost.
The minimum of this function occurs for that value of b that makes dc/db = 0. Thus, we have
This is zero when 1nb = 1, or b = e.
This is not a very satisfactory result. Because e ≈ 2.718, 2 and 3 must be the most efficient integral bases. Which is more efficient? The ratio of the cost of a base 2 register to the cost of a base 3 register is
Thus, base 2 is more costly than base 3, but only by a small amount.
By the same analysis, base 2 is more costly than base e by a factor of about 1.062.
Exercises
1. Schroeppel’s formula for converting from base –2 to binary has a dual involving the constant 0x5555555. Can you find it?
2. Show how to add 1 to a base –2 number using the arithmetic and logical operations of a binary computer. For example, 0b111 ⇒ 0b100.
3. Show how to round a base –2 number down (in the negative direction) to a multiple of 16 using the arithmetic and logical operations of a binary computer. For example, 0b10 ⇒ 0b110000.
4. Write a program, in a language of your choice, to convert a base – 1 + i integer to the form a + bi, where a and b are real integers. For example, if you give the program the integer 33, or 0x21, it should display something like 5 − 4i.
5. How would you convert a number in base − 1 + i to its negative? Extract its real part? Extract its imaginary part? Convert it to its complex conjugate? (The complex conjugate of a + bi is a − bi.)