How do you use bitwise operators to calculate 15 plus 7?
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;
}
Professor
Vivi
Beau
