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.

What is `first`? What does your failed attempt using `sizeof` look like, and how is it not working? — 1201ProgramAlarm, Nov 03 '21 at 21:10
@1201ProgramAlarm `first` is a class field of type `K`. I try to do this `first |= (flag * 8 * sizeof(K))` — th3g3ntl3man, Nov 03 '21 at 21:15
Please provide a [minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example) of what you have attempted. It is hard to understand exactly where each variable in your code came from. — Gary Strivin', Nov 03 '21 at 21:21
Try Exclusive Or. For a byte, performing `n ^ 0x80` will toggle the sign bit. — Thomas Matthews, Nov 03 '21 at 21:27
"Toggle" usually means "invert". This looks more like you want to *set* the bit to the value of `flag`. — Nate Eldredge, Nov 03 '21 at 21:41
Does this answer your question? [How do you set, clear, and toggle a single bit?](https://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit) — Giovanni Cerretani, Nov 05 '21 at 08:08

score 4 · Accepted Answer · answered Nov 03 '21 at 21:33

4

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);
}

answered Nov 03 '21 at 21:33

Lev M.

6,088
1
10
23

score 3 · Answer 2 · answered Nov 03 '21 at 21:28

3

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();
}

answered Nov 03 '21 at 21:28

NathanOliver

171,901
28
288
402

Can you show me how do this with bitwise operation? – th3g3ntl3man Nov 03 '21 at 21:33
1

@th3g3ntl3man See Lev M.'s answer – NathanOliver Nov 03 '21 at 21:33
This flips the msb, but the code in OP's answer is more like a "set msb". – Matteo Italia Nov 03 '21 at 21:58

Matteo Italia · Answer 3 · 2021-11-03T22:49:10.427

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).

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.

score 0 · Answer 4 · answered Nov 05 '21 at 08:26

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.

Set the most significant bit

This is the Item class:

4 Answers4

This is the `Item` class: