Arithmetic operators using bitwise operators

Question

Is there a way to perform addition(or arithmetic operations) by using ONLY bitwise operators?

yes! do dump assembly code for multiplication and division and you can see it for your self. eg: int a = 2; int twice_a = a << 1; // left shift is multiplication by two and like wise I would recommend "Hacker's Delight" book for other good stuff that you can do with bitwise operations — Sarang, Nov 08 '12 at 06:18
Possible duplicate of http://stackoverflow.com/questions/4068033/addition-of-two-integers-using-bitwise-operators. Answer to that question is given in C. — kevintodisco, Nov 08 '12 at 06:18
Petzold goes into this in a quite readable way in his book 'Code': http://www.charlespetzold.com/code/. — Simon Nickerson, Nov 08 '12 at 06:20
Not a duplicate. This is a superset question, whereas the other concerns only addition. — Thomas Eding, Nov 08 '12 at 06:20
Hardware is all bitwise operators, and eventually ALL operations are done in hardware, so yes. Even `log10` is done bitwise. — MSalters, Nov 08 '12 at 09:41

score 4 · Answer 1 · answered Nov 08 '12 at 06:18

4

You can search for some hardware designs for arithmetic operators. For addition example, you can find full adder, half adder, then ripple carry adder, carry save adder, carry lookahead adder. Then you can generate lots of code to use bit-wise operators to do those arithmetic operations.

answered Nov 08 '12 at 06:18

jclin

2,449
1
21
27

3

I would make it more clear in this answer that the *only* way that hardware performs addition and other arithmetic operations is with bitwise logical operations :) – kevintodisco Nov 08 '12 at 06:22
@ktodisco But from that it doesn't follow that C/C++ bitwise _operators_ can be used to describe these operations. There is a difference between bitwise operations in general, and the bitwise operators of C/C++. – jogojapan Nov 08 '12 at 06:27
@jogojapan There is? Yes the right shift is annoyingly unspecified, but you can fix that rather easily with a bit extra code and it's not as if implementing right shifts with a bit of looping and the more elemental bitwise operators was especially complicated. – Voo Nov 08 '12 at 07:03
@Voo What I mean is that for example the processor instruction ADD is of course a bitwise operation. When it is applied to two registers, it will perform addition by manipulating the bits in of the target register as necessary. But who says that this operation can be expressed using no more than `&`, `|`, `~`? (We know it can, but this doesn't follow trivially from the fact that ADD is applied in a bitwise manner.) – jogojapan Nov 08 '12 at 07:19
Hmm no, I don't see how from "Add is implemented using only bitwise operations" it doesn't follow that "We can implement add using only bitwise operations". Whether I do the operations on paper, in my head, in a high level language like c++ or using 32nm CMOS transistors is rather immaterial really. – Voo Nov 08 '12 at 07:25
@Voo That's not what I said. I said from "ADD is a bitwise operation (because it is performed as an operation on a bitwise representation of a number)" it does not follow that "this same bitwise operation can be expressed using the bitwise operators of C/C++". – jogojapan Nov 08 '12 at 07:32

Aki Suihkonen · Accepted Answer · 2012-11-08T11:38:18.310

Addition of bits a,b and c

carry_out = b&c|a&b|a&c;  // there's a carry, if at least 2 bits are set
sum = a^b^c;              // the sum is the number of set bits modulo 2

One has to perform this for all bits in the word - first for bit 0 using carry_in = c = 0, and iterating to carry_in(next_bit) = carry_out(previous_result).

Subtraction happens with bit inverting b from (a-b) and setting the initial carry to 1.

However, if one has to add e.g 32 numbers in parallel, one can fit 'a' with 32 lsbs of all those numbers and perform the binary operations in parallel. This is a technique called bit slicing.

For multiplication CSA (carry save adder is definitely the best software approach -- it has the smallest "area")

As an exercise, here's an algorithm that calculates a+b(+c) in parallel:

int a = 13113;
int b = 43334;
int c =     1;

int main()
{
   int sum=a^b^c,c2;
   c=((c&a)|(a&b)|(c&b))<<1;
   while (c) {
     c2=(c&sum)<<1;
     sum^=c;
    c=c2;
   }
   printf("%d\n",sum);
}

score 0 · Answer 3 · answered Nov 08 '12 at 06:31

Note that bitwise operators in C is only applicable to integral operands not on arithmetic operands

And yes you can do it using bitwise for all operations(+,-,*,/,%)

for e.g.

int a =10;
a<<1; // it's multiplication : a*2
a>>1; //it's division : a/2

I have shown this for 2 only. You can do for addition of two integers using the FULL ADDER (SUM and CARRY functios) for any number of bits

Arithmetic operators using bitwise operators

3 Answers3

Linked