Adding to a bit array

Question

In my program, I am using BitArrays to represent 160 bit numbers. I want to be able to add, subtract, increment and decrement these numbers, what is the algorithm for doing this?

At the moment I'm not interested in multiplication and division, but I might be in the future so bonus points for that.

I'm implementing in C#, but pseudocode is fine if you're not familiar with the language

Answer 1

Increment and decrement you can write by hand, and adding, substracing you may do it with write method. You know this method because you using in base school this method working on all numeric systems not only for base 2 and 10.

Like this:

100100
010110 +
--------
111010

Answer 2

Arrays of unsigned 8-bit bytes might make it much easier. Then you just have to add / subtract from the least significant byte and handle carrying.

There's plenty of information out there on binary addition.

Alternatively, you could save yourself some pain and re-use someone elses imlpementation :-)

Answer 3

Since you are using C#, you might want to take a look at BigInteger which was added to the recently released .NET 4.0.

Answer 4

There is a better way, high school maths uses the standard 'ripple carry' approach which has the disadvantage that you have to work one bit at a time. 'Carry look ahead' is the term you want to google or just read:

http://en.wikipedia.org/wiki/Carry_look-ahead_adder

It groups bits and does some clever logic to greatly reduce the number of steps to add the numbers together. There is a parallel process for subtraction I just can't remember the name.