`bit::vector` — Riffling

We have instance methods that make a copy of the bit-vector with its elements interleaved with zeros.

constexpr bit::vector riffled() const;

This method creates a new bit-vector, a copy of the current bit-vector with interleaved zeros. For example, if the current bit-vector has elements [a b c d], the returned bit-vector will have elements [a 0 b 0 c 0 d].

constexpr void riffled(bit::vector& dst) const;

This method turns dst into a copy of the current bit-vector with interleaved zeros. For example, if the current bit-vector has elements [a b c d], then, on return, the dst bit-vector will have elements [a 0 b 0 c 0 d]. It is helpful for algorithms that require repeated riffling and where we want to reuse the dst storage.

One reason this might be useful

If you think of a bit-vector \(\mathbf{p}\) as being the coefficients in a polynomial over \(\mathbb{F}_2\): \[ p(x) = p_0 + p_1 x + p_2 x^2 + \cdots \] It is easy to verify that the polynomial \(p(x)^2\) has coefficients that are the riffled version of \(\mathbf{p}\). For example, if \(p(x) = a + bx\) then \[ p(x)^2 = a^2 + 2 a b x + b^2 x^2 \] In \(\mathbb{F}_2\), you drop all multiples of 2, and it follows that \[ p(x)^2 = a + b x^2 \] The general case follows by induction.

The riffled version of a bit-vector of size \(n \ge 2\) will have size \(2n-1\). The riffled version of a bit-vector of size \(n < 2\) will be \(n\).

Example

#include <bit/bit.h>
int main()
{
    using vector_type = bit::vector<std::uint8_t>;
    std::size_t N = 17;
    auto u = vector_type::ones(N);
    auto v = u.riffled();
    std::cout << "u           = " << u << " has size " << u.size() << '\n';
    std::cout << "u.riffled() = " << v << " has size " << v.size() << '\n';
}

Output

u           = [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] has size 17
u.riffled() = [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1] has size 33

See Also