bitwise arithmetic tutorial

1
votes

I'm looking for tutorials which talk about bitwise arithmetic operations, such as addition, subtraction, multiplication and division, maybe other operators more complicated like modular, inverse modular etc.

Actually I'm trying to implement a big number library for an embedded system on which there is no such library. So I'd like to learn how to handle signed big integers and how to do arithmetic calculations by manipulating bits. Now the only idea I have is to hold my big integer in a big uint8_t array with 1 bit reserved for sign. For example, if I need a 160-bit integer, then I need an array uint8_t num[21].

What are the basic knowledge that I have to learn ? I've searched on Google but I haven't found many well explained tutorials. Or more exactly I don't know what are the keywords that I have to use.

So I need your suggestions. If you know where I can find interesting tutorials, please post links here. PDFs, web pages, videos anything.

3
cbit-manipulationbitwise-operatorsbiginteger
google and wikipedia should help. - Alexey Frunze
Are you planning to write this library in c? If yes, I don't understand why you need to know how to do arithmetic calculations by manipulating bits...The topic of combinatorial circuits is huge and not always trivial...Or maybe I just misunderstood your question. - Manlio
Maybe look at GNU MP, which is a bignum library implemented in C. - larsks
@Saphrosit Not in C, but I'll try with C at first, just get familiar with algorithms. - Allopopo
doing arithmetic operations with only bitwise operations is hugely inefficient - phuclv

3 Answers

1
votes

The topic you're interested in is called arbitrary precision arithmetic.

Further information can be found here: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

As far as "basic knowledge" is concerned: you will need to learn algorithms for performing arithmetic. you will also need a fairly competent understanding of dynamic memory management. I suspect your approach using arrays can be very clumsy and wasteful.

1
votes

Some week ago, while I was wandering on Stack Overflow, I found this article, maybe this can help you.

Unfortunately, I didn't see arithmetic operation on the first link I posted.

For an arithmetic operation, look here.

Electronic is same as in programming, same concept, since logical gate = logical operationoperation. In the "see also" section of that link, more thing to help. (especially the binary multiplier)

PM me if you succeed in what you are doing, I'm also looking to learn how it works.

0
votes

There's really no such thing as bitwise arithmetic (add, subtract, etc) but you can implement them using bitwise operations (AND, OR, XOR, logical left shift, logical right shift, arithmetic right shift).

See: http://en.wikipedia.org/wiki/Bitwise_operation