Performing Arithmetic on Bitsets

Problem

You want to perform basic arithmetic and comparison operations on a set of bits as if it were a binary representation of an unsigned integer number.

Solution

The functions in Example 11-36 provide functions that allow arithmetic and comparison of bitset class template from the header as if it represents an unsigned integer.

Example 11-36. bitset_arithmetic.hpp

#include 
#include 

bool fullAdder(bool b1, bool b2, bool& carry) {
 bool sum = (b1 ^ b2) ^ carry;
 carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
 return sum;
}

bool fullSubtractor(bool b1, bool b2, bool& borrow) {
 bool diff;
 if (borrow) {
 diff = !(b1 ^ b2);
 borrow = !b1 || (b1 && b2);
 }
 else {
 diff = b1 ^ b2;
 borrow = !b1 && b2;
 }
 return diff;
}

template
bool bitsetLtEq(const std::bitset& x, const std::bitset& y)
{
 for (int i=N-1; i >= 0; i--) {
 if (x[i] && !y[i]) return false;
 if (!x[i] && y[i]) return true;
 }
 return true;
}

template
bool bitsetLt(const std::bitset& x, const std::bitset& y)
{
 for (int i=N-1; i >= 0; i--) {
 if (x[i] && !y[i]) return false;
 if (!x[i] && y[i]) return true;
 }
 return false;
}

template
bool bitsetGtEq(const std::bitset& x, const std::bitset& y)
{
 for (int i=N-1; i >= 0; i--) {
 if (x[i] && !y[i]) return true;
 if (!x[i] && y[i]) return false;
 }
 return true;
}

template
bool bitsetGt(const std::bitset& x, const std::bitset& y)
{
 for (int i=N-1; i >= 0; i--) {
 if (x[i] && !y[i]) return true;
 if (!x[i] && y[i]) return false;
 }
 return false;
}

template
void bitsetAdd(std::bitset& x, const std::bitset& y)
{
 bool carry = false;
 for (int i = 0; i < N; i++) {
 x[i] = fullAdder(x[i], y[i], carry);
 }
}

template
void bitsetSubtract(std::bitset& x, const std::bitset& y) {
 bool borrow = false;
 for (int i = 0; i < N; i++) {
 if (borrow) {
 if (x[i]) {
 x[i] = y[i];
 borrow = y[i];
 }
 else {
 x[i] = !y[i];
 borrow = true;
 }
 }
 else {
 if (x[i]) {
 x[i] = !y[i];
 borrow = false;
 }
 else {
 x[i] = y[i];
 borrow = y[i];
 }
 }
 }
}

template
void bitsetMultiply(std::bitset& x, const std::bitset& y)
{
 std::bitset tmp = x;
 x.reset( );

 // we want to minimize the number of times we shift and add
 if (tmp.count( ) < y.count( )) {
 for (int i=0; i < N; i++)
 if (tmp[i]) bitsetAdd(x, y << i);
 }
 else {
 for (int i=0; i < N; i++)
 if (y[i]) bitsetAdd(x, tmp << i);
 }
}

template
void bitsetDivide(std::bitset x, std::bitset y,
 std::bitset& q, std::bitset& r)
{
 if (y.none( )) {
 throw std::domain_error("division by zero undefined");
 }
 q.reset( );
 r.reset( );
 if (x.none( )) {
 return;
 }
 if (x == y) {
 q[0] = 1;
 return;
 }
 r = x;
 if (bitsetLt(x, y)) {
 return;
 }

 // count significant digits in divisor and dividend
 unsigned int sig_x;
 for (int i=N-1; i>=0; i--) {
 sig_x = i;
 if (x[i]) break;
 }
 unsigned int sig_y;
 for (int i=N-1; i>=0; i--) {
 sig_y = i;
 if (y[i]) break;
 }

 // align the divisor with the dividend
 unsigned int n = (sig_x - sig_y);
 y <<= n;

 // make sure the loop executes the right number of times
 n += 1;

 // long division algorithm, shift, and subtract
 while (n--)
 {
 // shift the quotient to the left
 if (bitsetLtEq(y, r))
 {
 // add a new digit to quotient
 q[n] = true;
 bitsetSubtract(r, y);
 }
 // shift the divisor to the right
 y >>= 1;
 }
}

Example 11-37 shows how you might use the bitset_arithmetic.hpp header file.

Example 11-37. Using the bitset_arithmetic.hpp functions

#include "bitset_arithmetic.hpp"

#include 
#include 
#include 

using namespace std;

int main( ) {
 bitset<10> bits1(string("100010001"));
 bitset<10> bits2(string("000000011"));
 bitsetAdd(bits1, bits2);
 cout << bits1.to_string, allocator >( ) << endl;
}

The program in Example 11-37 produces the following output:

0100010100

 

Discussion

The bitset class template comes with basic operations for manipulating sets of bits but doesn't provide any arithmetic or comparion operations. This is because the library can't safely assume what kind of numerical type a programmer might expect an arbitrary set of bits to represent.

The functions in Example 11-36 treat a bitset as a representation of an unsigned integer type, and provide you with functions for adding, subtracting, multiplying, dividing, and comparing them. These functions can provide a basis for writing custom-sized integer types, and are used for such a purpose in Recipe 11.20.

I did not use the most efficient algorithms I could for Example 11-36. Instead I chose the simplest possible algorithms because they are more easily understood. A much more efficient implementation would use similar algorithms, but would operate on words rather than single bits.

See Also

Recipe 11.20