Set the most significant bit

Question

I'm trying to toggle the most significant bit of an unsigned int based on a bool flag. This is my code for an hypothetical K = unit64_t:

This is the Item class:

template<typename K>
class Item {
  public:
    K first;

    Item() = default;
    explicit Item(const K &elem, const bool flag = false) {
      first = elem & 0x3FFFFFFFFFFFFFFF;
      first |= (flag * 0x8000000000000000);
    }
};

Is there a way to do this fully generical? That it works for all kind of numeric K?

I tried with the 8 * sizeof(K) but it doesn't work.

Answer 1

An option using only bit operations:

template<typename T>
void Item(T& elem, bool flag = false) {
    T mask = (T)1 << (sizeof(T) * 8 - 1);
    elem = (elem & ~mask) | (flag ? mask : 0);
}

Answer 2

You can leverage std::bitset for this. Not sure how well this optimizes, but it should optimize well and it will work generically and requires no bitwise operation knowledge.

template <typename T>
void toggle_msb(T& val)
{
    constexpr auto bit_width = sizeof(T) * CHAR_BIT;
    std::bitset<bit_width> temp(val);
    val = temp.flip(bit_width - 1).to_ullong();
}

Answer 3

Using bitwise operations, but without explicitly depending on the size of T:

template<typename T>
T set_top_bit(T value, bool state) {
    constexpr T mask = T(~T(0)) >> 1;
    value &= mask;
    if (state) value |= ~mask;
    return value;
}

T(~T(0)) gets a T with all bits set¹; >> 1 throws out the bottom bit getting a 0 in from the top, so in mask we have a T with all bit set but the topmost. Notice that all this dance is purely formal—this is all evaluated at compile time.

The rest is pretty much like your code: mask out the top bit from value and OR it back in depending on state (~mask will be a T with only the top bit set).

---

1. Plain ~0 would result in an int set to -1, ~0U in an unsigned int with all bits set; to obtain a T with all bits set, we need to flip the bits of a T(0) (so, a 0 of our T type), and also to cast back to T later, because, if T is smaller than int, ~T(0) is actually equivalent to ~int(T(0)), so ~0, due to integer promotion rules.

Answer 4

From this great post, How do you set, clear, and toggle a single bit?, you can use this branchless version:

#include <climits>

template<typename T>
constexpr T set_top_bit_v2(T value, bool state) {
    constexpr auto msb = (sizeof(T) * CHAR_BIT) - 1;
    return (value & ~(T{1} << msb)) | (T{state} << msb);
}

Comparing the output with the version of Matteo Italia on Godbolt (here), despite the differences Clang seems to generate the same code, while GCC and MSVC seem to emit less instructions when using this version.