Kogge-Stone adder

kogge_stone_adder.cpp

#include <bitset>

// Kogge-Stone adder
template<std::size_t N>
struct carry
{
    std::bitset<N> g = 0;
    std::bitset<N> p = 0;
    static constexpr carry apply(carry x, carry y)
    {
        return {x.g | x.p & y.g, x.p & y.p};
    }
    constexpr carry operator<<(std::size_t pos) const
    {
        return{g << pos, p << pos};
    }

    constexpr std::bitset<N> compute() const
    {
        carry r = *this;
        for(std::size_t shift=1;shift<N;shift*=2)
        {
            r = apply(r, r << shift);
        }
        return r.g << 1;
    }
};

template<std::size_t N>
constexpr std::bitset<N> add(std::bitset<N> x, std::bitset<N> y)
{
    return x ^ y ^ carry<N>{x & y, x | y}.compute();
}