(For best results, view this article in a fixed-pitch font such as Courier.)

Sri said:

How do you add an n-bit number in C?

Presumably you mean "add an n-bit number to an m-bit number", where at least

one of the numbers - or perhaps the result - is too big to store in an int.

Consider how you would add two 1-bit numbers, and for now let's ignore the

concept of "carry", and just focus on a 1-bit result.

0 0 1 1 M

+ 0 + 1 + 0 + 1 N

- - - -

0 1 1 0 M + N (no carry)

Easy, right?

Curiously, we can see that the results we get are just the same as if,

instead of adding-without-carry, we had used the XOR operator. So, if carry

doesn't matter, we can add two numbers by simply XORing them together.

But carry /does/ matter. Let's look at the carry, then.

0 0 1 1 M

+ 0 + 1 + 0 + 1 N

- - - -

0 1 1 0 M + N (no carry)

(0) (0) (0) (1) M + N (carry only)

Here, the carry figures are always zero UNLESS the M bit AND the N bit are

both set. So now we have a way to calculate the carry.

Let's do these steps on a couple of longer bitstrings, and see where it

takes us. We'll use M = 11011001 and N = 01011011 (chosen at random, and

remember these are binary strings, not ints!). M is longer than N, so I've

left-padded N with a 0. If it were longer still, I'd just have used more

0s! Don't pay any attention to the fact that I've used 8-bit examples. If

you have bitstrings longer than 8 bits, simply use an array of unsigned

integers (personally, I use an array of unsigned char, although for

performance reasons you might prefer types such as unsigned int or unsigned

long), and keep your indices straight.

So - here's the technique:

11011001 M

+ 01011011 N

The first step is to get the result without carry. To do this, we XOR the

two values together, storing the result in X:

11011001 M

+ 01011011 N

--------

10000010 X = M ^ N (partial result)

The second step is to calculate the carry, storing the result in C:

11011001 M

+ 01011011 N

--------

01011001 C = M & N (partial result)

Now, a carry bit indicates that we should "carry" the result over to the

next column to the left. We can easily do that using a LEFT SHIFT. So let's

do that, storing the result in S:

01011001 C

--------

10110010 S = C << 1 (partial result)

If only this carry were 00000000, we'd have finished, and our result would

be in X. But this carry is *not* 00000000. So to get our proper result,

then, we need to add this shifted carry result back into our original

XOR-style addition. How do we do this? In the same way as before, that's

how. But this time we're adding X and S. If we're prepared to destroy M and

N (hey, we can copy them first, right?), we can keep down the number of

symbols. So M = X, and N = S

10000010 M

+ 10110010 N

--------

00110000 X = M ^ N (partial result)

Now the carry:

10000010 M

+ 10110010 N

--------

10000010 C = M & N (partial result)

The carry is not all-bits-zero, so we haven't finished yet. Let's shift the

carry:

10000010 C

--------

100000100 S = C << 1 (partial result)

Oops - we used a ninth bit (you have to be careful here - when you're

shifting a value left and wish to preserve bits, you need to check the high

bit to see if it's set; if so, you'll need to stretch your memory a little;

this is easily accomplished using realloc or the like; if you don't know

how to do efficient memory-stretching in C, yell and someone will no doubt

explain. Right now, let's not get distracted).

M = X (except that we'll need to left-pad it with a 0-bit - no big deal).

N = S

000110000 M

+ 100000100 N

---------

100110100 X = M ^ N (partial result)

Now the carry:

000110000 M

+ 100000100 N

---------

000000000 C = M & N (partial result)

The carry is NOW all-bits-zero, so we're done! And the result is in X.

Let's check the result. X = 100110100, which is 256 + 32 + 16 + 4 which is

308. Let's look at our original values: 11011001 which is 128 + 64 + 16 + 8

+ 1 which is 217, and 01011011 which is 64 + 16 + 8 + 2 + 1 which is 91.

And if my abacus doesn't deceive me, 217 + 91 is 308. So the result is

correct.

Don't forget to handle the concept of "sign". Personally, I prefer a

"sign-and-magnitude" representation for this kind of thing - I have a

struct which looks like this:

{

int sign; /* -1,0,1 */

size_t mag; /* number of significant bytes (at least 1) */

size_t cap; /* mallocated storage capacity, >= mag */

unsigned char *n; /* the pointer to the number byte array */

};

Clearly, n has to be pointed at a useful amount of storage. I use the "cap"

member to record the number of bytes to which n points (the "capacity"),

and "mag" to record the number of bytes used by the number currently being

stored. If mag is in danger of exceeding cap, I realloc.

Now, if either M or N is 0, then clearly the other value gives the result of

the addition. Otherwise, if M is negative (M->sign < 0), I simply make it

positive (temporarily!) by changing M->sign to 1, and then pass it to my

subtraction routine. (Then, of course, I make it negative again.)

Likewise for N.

Incidentally, the subtraction routine does similar juggling, so if M and N

are *both* negative, I pass -M and N to the subtraction routine, which then

passes -M and -N to the addition routine! (You have to be careful about the

parameter order, of course, but if you get it right, then it all comes out

in the wash.)

Multiplication is a snap if you're prepared to use a couple of loops - just

keep shifting and adding the results of byte-by-byte multiplications until

you run out of things to multiply.

Division is another matter. It's a bit scary, and Knuth is your friend.

Perhaps the easiest way to understand division is to reduce it to binary. If

you do this, you will find that you need only know your 1-times table! Any

bit sequence "goes into" any other bit sequence of the same length either

once, or not at all. So to divide 100100101 by 110001, you just do this

(each step shown separately):

..000000

110001 ) 100100101

110001

..0000001

110001 ) 100100101

0110001

-------

0011000

..00000010

110001 ) 100100101

0110001

-------

00110000

110001

..000000101

110001 ) 100100101

0110001

-------

001100001

000110001

---------

000110000

So the result of 100100101 (293 dec) divided by 110001 (49 dec) is 101 (5

decimal) remainder 110000 (48 decimal). Check: 5 * 49 = 245, + 48 is 293.

Wrap that up in unsigned chars, and you have division. But there are faster

ways. See Knuth's "The Art of Computer Programming", Volume 2.

--

Richard Heathfield

"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)