Implementing a four-bit adder with C++ template metaprogramming

I recently read a post by Phillip Larkson where the C preprocessor was used to implement a four-bit adder entirely at compile time. This got me wondering whether I could implement the same concept using C++ template metaprogramming. It seemed theoretically possible as all the components can be calculated at runtime, but I wanted to avoid making use of the preprocessor for anything but supplying the original values to be added. The goal was to compile something on the command line like:

clang -DNUMBER_1=5 -DNUMBER_2=7 foo.cpp

and have the value 12 written out to the command line.

It turns out that this is relatively straight-forward to implement in C++. You can encode the bitwise operators AND and XOR with template specializations, and the remainder of the adder is bookkeeping for the sum and carry bits. The bitwise operators and adder themselves look like:

struct one_bit {
  static const unsigned value = 1;
};

struct zero_bit {
  static const unsigned value = 0;
};

template <unsigned A1, unsigned B1>
struct and_op : public zero_bit {};

template <>
struct and_op<1, 1> : public one_bit{};

template <unsigned A1, unsigned B1>
struct xor_op : public zero_bit {};

template <>
struct xor_op<1, 0> : public one_bit{};

template <>
struct xor_op<0, 1> : public one_bit{};

template <unsigned A1, unsigned B1, unsigned cin>
struct full_adder {
  static const unsigned sum = xor_op<xor_op<A1, B1>::value, cin>::value;
  static const unsigned carry = xor_op<and_op<xor_op<A1, B1>::value, cin>::value, and_op<A1, B1>::value>::value;
};

I define a pair of base structures to represent a zero bit and a one bit. The base operator is not specialized, and results in the zero bit. The specializations for the operators return the one bit for the correct operands. The full_addr structure implements the typical sum and carry operations which are described on Wikipedia.

As I mentioned, implementing the four-bit adder is a matter of bookkeeping for the bits, and so I made a helper structures called two_bit_addr and four_bit_addr_inner to do the bookkeeping. The implementation of each is to hook up the full_addr in a serialized fashion. I suspect there’s a way to make a generalized N-bit adder using template parameter packing, but I didn’t give the design enough though to prove it’s possible.

template <unsigned A0, unsigned A1, unsigned B0, unsigned B1, unsigned C0>
struct two_bit_adder {
private:
  static const unsigned c1 = full_adder<A0, B0, C0>::carry;

public:
  static const unsigned s0 = full_adder<A0, B0, C0>::sum;
  static const unsigned s1 = full_adder<A1, B1, c1>::sum;
  static const unsigned carry = full_adder<A1, B1, c1>::carry;
};

template <unsigned A3, unsigned A2, unsigned A1, unsigned A0,
  unsigned B3, unsigned B2, unsigned B1, unsigned B0,
  unsigned C0>
struct four_bit_adder_inner {
private:
  static const unsigned c1 = two_bit_adder<A0, A1, B0, B1, C0>::carry;

public:
  static const unsigned s0 = two_bit_adder<A0, A1, B0, B1, C0>::s0;
  static const unsigned s1 = two_bit_adder<A0, A1, B0, B1, C0>::s1;
  static const unsigned s2 = two_bit_adder<A2, A3, B2, B3, c1>::s0;
  static const unsigned s3 = two_bit_adder<A2, A3, B2, B3, c1>::s1;
  static const unsigned carry = two_bit_adder<A2, A3, B2, B3, c1>::carry;
};

In order to fit the design I wanted, I needed some helpers that would convert a decimal value into a series of binary digits, and binary digits into a decimal value. This way, I could specify decimal values on the command line, convert them into binary values to pass to the adder, and then convert the binary result from the adder back into a decimal value.

The binary conversion uses recursive template definitions to determine each bit of the value. Given a decimal input and a bit index, it returns the bit value at that index.

template <unsigned N, unsigned BN>
struct to_bin_helper {
  static const unsigned value = to_bin_helper<(N >> 1), BN - 1>::value;
};

template <unsigned N>
struct to_bin_helper<N, 0> : to_bin_helper<N & 1, 0>{};

template <>
struct to_bin_helper<1, 0> : one_bit{};

template <>
struct to_bin_helper<0, 0> : zero_bit{};

template <unsigned Num, unsigned Bit>
struct to_bin {
  static const unsigned value = to_bin_helper<Num, Bit>::value;
};

To convert from binary back to decimal, I used template parameter packing from C++ to represent the bits in the binary number, and the resulting value is a straight binary-to-decimal calculation using recursive template definitions to perform the calculation. This, of course, requires the ability to get power-of-two values for which I used another recursive template definition.

template <unsigned N>
struct pow2 {
  static const unsigned value = 2 * pow2<N - 1>::value;
};

template <>
struct pow2<0> {
  static const unsigned value = 1;
};

template <unsigned N, unsigned S, unsigned... Rest>
struct to_dec_helper {
  static const unsigned value = (S * pow2<N>::value) + to_dec_helper<N + 1, Rest...>::value;
};

template <unsigned N, unsigned S>
struct to_dec_helper<N, S> {
  static const unsigned value = S * pow2<N>::value;
};

template <unsigned Bit1, unsigned... BitN>
struct to_dec {
  static const unsigned value = to_dec_helper<0, Bit1, BitN...>::value;
};

Finally, I could put all of these helpers together to create the four-bit adder structure. It accepts two decimal values which are converted into binary values when passed to the inner four-bit adder helper. The inner helper performs the calculation and returns the bits for the result. These bits are then passed into the binary-to-decimal helper which returns the resulting decimal value. All of this happens within the template system and results in a constant value.

template <unsigned A, unsigned B>
struct four_bit_adder {
  static const unsigned value = to_dec<four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value,
                                                            to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value,
                                                            0>::s0,
                                       four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value,
                                                            to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value,
                                                            0>::s1,
                                       four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value,
                                                            to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value,
                                                            0>::s2,
                                       four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value,
                                                            to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value,
                                                            0>::s3
                                       >::value;
};

The resulting program is trivial — it expects the values to be added to come from the command line via the preprocessor:

int main(void) {
  static const unsigned ret = four_bit_adder<NUMBER_1, NUMBER_2>::value;
  ::printf("%d\n", ret);
  return 0;
}

Executing it from the command line results in the expected values:

E:\llvm\2013>clang -std=c++11 -DNUMBER_1=7 -DNUMBER_2=4 "E:\Aaron Ballman\Deskto
p\test.cpp"

E:\llvm\2013>a.out
11

E:\llvm\2013>clang -std=c++11 -DNUMBER_1=9 -DNUMBER_2=4 "E:\Aaron Ballman\Deskto
p\test.cpp"

E:\llvm\2013>a.out
13

Thanks to Phillip for giving me the idea to do this! The full source code can be downloaded from here, and it’s been tested and works with clang 3.4 (ToT), gcc 4.8.1 and Visual Studio 2013.