1

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

Martin
  • 12,469
  • 13
  • 64
  • 128
  • BitArrays is not the best tool for calculations. – H H Apr 26 '10 at 23:20
  • Same as in middle school, with binary instead of decimal (or if you want to take better advantage of the hardware, in base 2**16, 2**32 or whatever is convenient for you). – Pascal Cuoq Apr 26 '10 at 23:23
  • I know bit arrays aren't ideal, but a vast amount of my code is doing individual bit twiddling, and I very rarely actually do any arithmetic operations. Hence, bit arrays – Martin Apr 26 '10 at 23:24
  • @The people saying high school maths. I'm aware of this, I was wondering if there was a clever bit twiddling method – Martin Apr 26 '10 at 23:25
  • Why the downvote? And why no comment? It's extremely rude to downvote without a comment! – Martin Apr 29 '10 at 23:54

4 Answers4

2

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

Wim Coenen
  • 66,094
  • 13
  • 157
  • 251
1

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.

Daniel
  • 1,994
  • 15
  • 36
  • Carry look-ahead doesn't save any steps, in fact it uses more steps. It is only useful to increase the parallelism of addition, which isn't very useful in software for the size of numbers the poster is talking about (it is very popular in hardware adders, however). Carry-save addition could potentially be useful if the poster has lots of numbers to add (or is going to do multiplies), but it doesn't sound like this is the case. – Keith Randall Apr 27 '10 at 06:59
0

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
Svisstack
  • 16,203
  • 6
  • 66
  • 100
0

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 :-)

Jon Cage
  • 36,366
  • 38
  • 137
  • 215
  • How is an array of bytes any easier? It's faster for sure, but the algorithms are basically the same whether you are using bits, bytes, words, whatever. – President James K. Polk Apr 26 '10 at 23:31
  • Indeed, carrying is the main problem with adding, and that's the same with bits or bytes – Martin Apr 26 '10 at 23:32
  • I'm not all that familiar with C#'s implementation of a BitArray, but I guessed from your post that it doesn't include arithmetic operators? ..unsigned char's _do_ have native arithmetic operators you can make use of. – Jon Cage Apr 27 '10 at 00:23