generic_binary_counter.cpp

template<typename Iterator, typename Value, typename BinaryOp>
Value add_to_counter(Iterator first, Iterator last,
                     Value carry, Value const &zero,
                     BinaryOp op)
{
    assert(carry != zero);
    for (; first != last; ++first) {
        if (*first == zero) {
            *first = carry;
            return zero;
        }
        carry = op(*first, carry);
        *first = zero;
    }
    return carry;
}

template<typename Iterator, typename Value, typename BinaryOp>
Value reduce_counter(Iterator first, Iterator last,
                     Value const &zero, BinaryOp op)
{
    first = std::find_if(first, last, [&zero](auto &v) { return v != zero; });
    if (first == last)
        return zero;

    Value result = *first;
    for (++first; first != last; ++first) {
        if (*first != zero)
            result = op(*first, result);
    }
    return result;
};


template<typename BinaryOp, typename Value>
class binary_counter {
public:
    binary_counter(BinaryOp const &op, Value const &zero)
        : m_bits(), m_zero(zero), m_op(op) {}

    void add(Value carry) {
        carry = add_to_counter(begin(m_bits), end(m_bits), carry, m_zero, m_op);
        if (carry != m_zero)
            m_bits.push_back(std::move(carry));
    }

    Value reduce() const {
        return reduce_counter(begin(m_bits), end(m_bits), m_zero, m_op);
    }

private:
    std::vector<Value> m_bits;
    Value m_zero;
    BinaryOp m_op;
};