How do you use bitwise operators to calculate 15 plus 7?

Answer 1

Normally you wouldn't, you'd simply use the built-in addition operator (+):

x = 15 + 7; // e.g., x = 22

However, Behind the Scenes, the computer uses bitwise operations to determine the sum and it is presumed the question relates to how this is actually achieved. In other words, how can we emulate these machine-level operations in code?

We start with a half-adder. A half-adder has two input bits, the two bits being summed (denoted A and B), and two output bits, the sum bit and the carry-out bit (denoted S and Cout). The half-adder truth table looks like this:

A + B = S, Cout

0 + 0 = 0, 0

0 + 1 = 1, 0

1 + 0 = 1, 0

1 + 1 = 0, 1

The sum bit is determined using a XOR gate (A XOR B) while the carry-out bit is determined using an AND gate (A AND B).

By itself, a half-adder only works for the least-significant bit of a sum (it is just a 1-bit adder after all). To sum multi-bit values we need to implement a full-adder for each bit in the sum. A full-adder is more difficult to implement than a half-adder because it has three inputs rather than just two.

One of the inputs is the carry-in bit (denoted Cin), which is actually the Cout bit from the full-adder for the next least-significant bit. Thus to sum two multi-bit values we use a cascade of full-adders, one for each bit in the sum, where the Cout from one full-adder becomes the Cin for the next.

A full-adder has the following truth table:

Cin + A + B = S, Cout 0 + 0 + 0 = 0, 0

0 + 0 + 1 = 1, 0

0 + 1 + 0 = 1, 0

0 + 1 + 1 = 0, 1

1 + 0 + 0 = 1, 0

1 + 0 + 1 = 0, 1

1 + 1 + 0 = 0, 1

1 + 1 + 1 = 1, 1

A full-adder is implemented using two half-adders joined by an OR gate. Input bits A and B pass through the first half-adder to produce a partial sum. The SUM bit of that half-adder then passes through the second half-adder along with the Cin bit to produce the final SUM bit of the full-adder. Meanwhile, the Cout bits from both half-adders pass through an OR gate to determine the Cout bit of the full-adder. That is, if the Cout bit is set by either of the half-adders, then the Cout must also be set for the full-adder.

Going back to the original example, the sum of 15 and 7, we proceed as follows:

15 + 7 in binary is 00001111 + 00000111

We start at bit 0 (least-significant bit) and pass the inputs through a cascade of full-adders, passing the Cout bit from one full-adder through the Cin to the next:

Cin + A + B = S, Cout

0 + 1 + 1 = 0, 1

1 + 1 + 1 = 1, 1

1 + 1 + 1 = 1, 1

1 + 1 + 0 = 0, 1

1 + 0 + 0 = 1, 0

0 + 0 + 0 = 0, 0

0 + 0 + 0 = 0, 0

0 + 0 + 0 = 0, 0

Reading the S column upwards we find the sum is 00010110 which is 22 decimal. Note that if the Cout of the final-adder is set, the sum has overflowed

To emulate these machine-level operations in C++, we first need to create a class to hold the two output bits:

struct output {

unsigned sum;

unsigned cout;

};

Note that an unsigned data type will occupy more than one bit, however the only valid values will be 0 or 1. Implementing this as a class would make it easier to maintain this invariant, however we'll use a simple data structure for the sake of brevity.

To implement the half-adder, we use the following code:

output half_adder (unsigned a, unsigned b) {

// both inputs must be in the range [0:1]

return output {a^b, a&b};

}

To implement the full-adder, we use the following code:

output full-adder (unsigned cin, unsigned a, unsigned b) {

// all inputs must all be in the range [0:1]

output one {half_adder (a, b)};

output two {half_adder (one.sum, cin)};

return output {two.sum, one.cout | two.cout};

}

To add two 8-bit values using the full-adder, we use the following code:

unsigned sum_8bit (unsigned a, unsigned b} {

unsigned sum=0;

output out {0, 0};

for (unsigned i=0; i<8; ++i) {

out=full_adder (out.cout, a&1, b&1);

sum|=(out.sum<<i);

a>>=1;

b>>=1;

}

if (out.cout) throw std::range_error {"sum_8bit(): out of range"};

return sum;

}

We can test the code with a simple assertion:

int main() {

assert (sum (15, 7)==22);

return 0;

}