9
\$\begingroup\$

When I was looking to use std::bitset instead of GCC's __uint128 in my RDS error-corrector, I found that it was hard to use, because there's no way to widen or truncate a bitset to one of another size. Nor is there any ability to do bitwise arithmetic (&, |, ^) or comparison (==, !=) with a bitset of different width.

I've identified the functions that I believe ought to be part of std::bitset and implemented them by wrapping the standard class. To convert between different widths, I've had to go via std::string, but (as written in comment), an update to std::bitset would have a more direct (and exception-free) path.

I could have composed rather than inherited std::bitset - that's not really of concern here. Please ignore the mechanics that deal with my::bitset being different to std::bitset and imagine that they are a single, larger class. I'm most interested in whether the function signatures are correct and complete.

Note that (like the integers), widening can be implicit, but narrowing operations need to be explicit. Most of the apparent duplication is to handle this distinction.

#include <bitset>
#include <climits>
#include <type_traits>
#include <utility>

namespace my {

    template<std::size_t N>
    struct bitset : public std::bitset<N>
    {
        // forwarding of std::bitset constructors
        bitset()
            : std::bitset<N>{}
        {}

        template<typename T>
        requires std::is_unsigned_v<T>
        bitset(T n)
            : std::bitset<N>{n}
        {}

        template< class CharT, class Traits, class Alloc >
        explicit bitset(const std::basic_string<CharT,Traits,Alloc>& str,
                        typename std::basic_string<CharT,Traits,Alloc>::size_type pos = 0,
                        typename std::basic_string<CharT,Traits,Alloc>::size_type n =
                        std::basic_string<CharT,Traits,Alloc>::npos)
            : std::bitset<N>{str, pos, n}
        {}

        // Widening and narrowing constructors, to be added to std::bitset

        // Although this user implementation round-trips through
        // std::string (which can throw std::bad_alloc), library
        // implementation can, and should, just copy the internal
        // representation.

        // widening conversion
        template<std::size_t P>
        requires P <= N
        bitset(const std::bitset<P>& n) noexcept
            : std::bitset<N>{n.to_string()}
        {}

        // narrowing conversion
        template<std::size_t P>
        requires P > N
        explicit bitset(const std::bitset<P>& n) noexcept
            : std::bitset<N>{n.to_string()}
        {}
    };

    // Deduction guide for my::bitset
    template<std::size_t N>
    bitset(std::bitset<N>) -> bitset<N>;


    // Free functions to be added to namespace std

    // Deduction guide
    template<typename T>
    requires std::is_unsigned_v<T>
    bitset(T) -> bitset<sizeof (T) * CHAR_BIT>;


    // comparisons - widen as necessary
    template<std::size_t N, std::size_t Q>
    constexpr auto operator==(const bitset<N>& a, const bitset<Q>& b)
        requires N != Q
    {
        if constexpr (N > Q)
            return a == bitset<N>{b};
        else
            return bitset<Q>{a} == b;
    }

    template<std::size_t N, std::size_t Q>
    constexpr auto operator!=(const bitset<N>& a, const bitset<Q>& b)
    {
        return ! (a == b);
    }

    // bitwise-and produces the narrower type
    // (a specific exception to "doing as the integers do")
    template<std::size_t N, std::size_t Q>
    constexpr auto operator&(const bitset<N>& a, const bitset<Q>& b)
        requires N!=Q
    {
        if constexpr (N > Q)
            return bitset<Q>(a) & b;
        else
            return a & bitset<N>(b);
    }

    template<std::size_t N, std::size_t Q>
    constexpr auto operator&(const bitset<N>& a, const bitset<Q>& b)
        requires N<Q
    {
        return a & bitset<N>(b);
    }

    // bitwise-and assignment accepts a wider type
    template<std::size_t N, std::size_t Q>
    constexpr auto operator&=(bitset<N>& a, const bitset<Q>& b)
        requires N != Q
    {
        return a &= bitset<N>(b);
    }

    // bitwise-or produces the wider type
    template<std::size_t N, std::size_t Q>
    constexpr auto operator|(const bitset<N>& a, const bitset<Q>& b)
        requires N<Q
    {
        return bitset<Q>{a} | b;
    }

    template<std::size_t N, std::size_t Q>
    constexpr auto operator|(const bitset<N>& a, const bitset<Q>& b)
        requires N>Q
    {
        return a | bitset<N>{b};
    }

    template<std::size_t N, std::size_t Q>
    constexpr auto& operator|=(bitset<N>& a, const bitset<Q>& b)
        requires N>=Q
    {
        return a = a | bitset<N>{b};
    }

    // bitwise-xor produces the wider type
    template<std::size_t N, std::size_t Q>
    constexpr auto operator^(const bitset<N>& a, const bitset<Q>& b)
        requires N<Q
    {
        return bitset<Q>{a} ^ b;
    }

    template<std::size_t N, std::size_t Q>
    constexpr auto operator^(const bitset<N>& a, const bitset<Q>& b)
        requires N>Q
    {
        return a ^ bitset<N>{b};
    }

    template<std::size_t N, std::size_t Q>
    constexpr auto& operator^=(bitset<N>& a, const bitset<Q>& b)
        requires N>=Q
    {
        return a = a ^ bitset<N>{b};
    }

    template<std::size_t N, typename T>
    requires std::is_unsigned_v<T>
    constexpr auto operator^(const bitset<N>& a, const T& b)
    {
        return a ^ bitset<N>{b};
    }
    template<std::size_t N, typename T>
    requires std::is_unsigned_v<T>
    constexpr auto operator^(const T& a, const bitset<N>& b)
    {
        return bitset<N>{a} ^ b;
    }

}

I've used Concepts Lite, which needs to be enabled when compiling as C++17. My compiler invocation is

g++ -std=c++17 -fconcepts \
   -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic \
   -Warray-bounds -Wno-unused -Weffc++

I have a simple compilation test for the above code. None of the mixed-width operations marked // new will compile with std::bitset; all the uncommented statements are fine with my::bitset. The commented-out statements are intended to be errors (because they have a narrowing conversion without a cast).

#define NEW_BITSET

int main()
{
#ifdef NEW_BITSET
    using my::bitset;
#else
    using std::bitset;
#endif

    // Lower-case variables are narrow; upper-case are wide

    bitset<32> a{0xFFFF0000u};
    bitset<64> B{a ^ 0xFFFF00u};

    //bitset<32> b = B;         // error
    bitset<32> b{B};            // explicit conversion
    //auto b = bitset<32>{B};   // error

    bitset c = a & B;           // new;  c  is bitset<32>
    bitset D = a | B;           // new;  D  is bitset<64>
    bitset E = a ^ B;           // new;  E  is bitset<64>

    c &= b;                     // no change
    c &= B;                     // new (unlike |= and ^=)
    B &= c;                     // new

    c |= b;                     // no change
    //c |= B;                   // error
    D |= b;                     // new

    c ^= b;                     // no change
    //c ^= B;                   // error
    D ^= b;                     // new
}

Perhaps there's a way to static_assert() that something shouldn't be valid, but I resorted to uncommenting the // error lines one at a time to prove them wrong.

\$\endgroup\$
  • \$\begingroup\$ Why do you have to go through std::string? Can't you copy bit by bit? \$\endgroup\$ – L. F. Jun 14 at 4:50
  • 1
    \$\begingroup\$ Bit-by-bit would work too, and would be noexcept. The point really is that if this were part of std::bitset, the implementation would be able to use its underlying representation, and could likely just std::memcpy() the data. \$\endgroup\$ – Toby Speight Jun 14 at 7:22
3
\$\begingroup\$

One aspect that could surprise users is that operator & always narrows types to match. That's a departure from the usual guidance of "do what the integers do".

On one hand, it makes sense not to waste resources on bits that will always be zero. One of my own use cases is to extract the some or all of the lower 26 bits from a 130-bit value, so it seems reasonable to expect a 26-bit result.

On the other hand, it could catch users out when shifting the result. These two functions will give different results:

auto fun_i(std::uint32_t a, std::uint16_t b) {
    return (a & b) << 16;
}

auto fun_b(my::bitset<32> a, my::bitset<16> b) {
    return (a & b) << 16;
}

On balance, I think that having to explicitly widen before shifting is a fair price to pay for saving resources when masking large numbers, but that would need to be well documented. And I value dissenting opinions (in comments, please).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.