How to avoid bitwise operations outside the width of the data type in c++

Question

For sake of experiment lets have a function that takes in a bitmask and offset and returns the mask shifted by offset. What would be a performance friendly way to determine if the operation will not shift any parts of the bitmask past the width of the data type? This is what I've tried so far, but maybe there is more optimal way to check this?

Example program: (Note: I'm looking for a solution for all data types, not only 16 bit integers)

#include <iostream>

using namespace std;

uint16_t TestFunc(uint16_t offset, uint16_t mask)
{
    if (offset >= sizeof(uint16_t) * 8)
        throw std::exception("Offset outside bounds");

    // find the index of the left-most bit in the mask
    int16_t maskLeftBitIndex = 0;
    uint16_t maskCopy = mask;

    while (maskCopy >>= 1)
        maskLeftBitIndex++;

    // check if the said left-most bit will be shifted past the width of uint16_t
    if (offset + maskLeftBitIndex >= sizeof(uint16_t) * 8)
        throw std::exception("Mask will end up outside bounds");

    return mask << offset;
}

int main()
{
    try
    {
        uint16_t test = TestFunc(15, 2);

        cout << "Bitmask value: " << test;
    }
    catch (std::exception& e)
    {
        cout << "Exception encountered: " << e.what();
    }

    return 0;
}

I _think_ (not tested) that it'd be more performance friendly to not throw but to just return the value unshifted (and test for that afterwards) and I think finding the index of the left-most bit in the mask could be done with [`std::bit_width`](https://en.cppreference.com/w/cpp/numeric/bit_width) pretty efficiently. — Ted Lyngmo, Oct 19 '21 at 13:34
maybe you can store the shifted value to a larger type. then check the truncated result. — apple apple, Oct 19 '21 at 13:37
@TedLyngmo I wasn't aware of std::bit_width. That seems to be what I'm looking for. I wonder if there is an implementation for C, or something that works with older versions of c++? — Gregor Sattel, Oct 19 '21 at 13:42
@appleapple this is still not safe, depending on the data type. What if you work with 64 bit bitmasks in the first place. — Gregor Sattel, Oct 19 '21 at 13:42
@GregorSattel it's safe for unit16 as in your code, and I'm not sure why it would be unsafe (despite unapplicable). — apple apple, Oct 19 '21 at 13:44
@appleapple You are right the question was a bit misleading - edited it so that it's stated that I'm not interested only in 16 bit integers. — Gregor Sattel, Oct 19 '21 at 13:45
@GregorSattel I don't know if C has added a function for that. If not, the compiler vendor probably has a built-in for that if you don't mind using such extensions. — Ted Lyngmo, Oct 19 '21 at 13:48
@GregorSattel: C has no standard equivalent of `std::bit_width`, but see https://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i for possible implementations. Also obligatory to refer to https://graphics.stanford.edu/~seander/bithacks.html, under "Finding integer log base 2 of an integer". — Nate Eldredge, Oct 19 '21 at 13:48
`if (offset >= sizeof(uint16_t) * CHAR_BIT || (mask << offset >> offset) != mask) { overflow }` — Raymond Chen, Oct 19 '21 at 14:05
@RaymondChen I believe it doesn't work due to integral promotion. — apple apple, Oct 19 '21 at 14:10
@appleapple Good point. `(uint16_t)(mask << offset) >> offset` then. — Raymond Chen, Oct 19 '21 at 14:46

apple apple · Accepted Answer · 2021-10-19T14:24:14.643

Not sure would this be faster, but you can check whether before and end value have same number of bits set

uint16_t TestFunc(uint16_t offset, uint16_t mask)
{
    if (offset >= std::numeric_limits<uint16_t>::digits)
        throw "Offset outside bounds (Possible Undefined Behavior)";
    
    uint16_t result = mask << offset;
    if(std::popcount(mask)!=std::popcount(result))
        throw "Offset outside bounds";
   
    return result;
}

score 0 · Answer 2 · answered Oct 19 '21 at 14:50

Here is the start of an example (not tested for signed integers) I made.

#include <cassert>
#include <cstdint>
#include <utility>
#include <stdexcept>

// instead of "real" exceptions, use return based exceptions
// kind of in the spirit of what Herb Sutter wants to do 
// with exceptions in the future too
enum class shift_result_exception
{
    none,
    invalid_arg,
    out_of_range
};

// struct to hold a return value and an "exception"
template<typename type_t>
struct shift_result_t
{
    shift_result_exception exception{ shift_result_exception::invalid_arg };

    type_t value{};

    operator type_t()
    {
        return value;
    }
};

// the actual shift logic.
template<typename type_t>
auto shift_left(const type_t value, const std::size_t shift)
{
    shift_result_t<type_t> result;

    // if caller wants to shift more places then the size of the type
    // this will be an invalid_arg result
    std::size_t type_size = sizeof(type_t) << 3; // = *8
    if (shift >= type_size) return result;

    // number of bits at front of value to check
    type_t mask = (1 << shift) - 1; 
    std::size_t mask_shift = (type_size - shift);
    // shift ones to the front of the type if any of the ones

    mask <<= mask_shift;

    // overlaps with a one of the value then the value cannnot be shifted
    // and the shifted value would go out of range
    if ((mask & value) != 0)
    {
        result.exception = shift_result_exception::out_of_range;
        return result;
    }

    // it is safe to shift.
    result.value = value << shift;
    result.exception = shift_result_exception::none;
    return result;
}

int main()
{
    assert(shift_left<int>(1, 1) == 2);
    assert(shift_left<std::uint8_t>(1, 7) == 128);
    assert(shift_left<std::uint8_t>(2, 7).exception == shift_result_exception::out_of_range);
    assert(shift_left<std::uint8_t>(1, 8).exception == shift_result_exception::invalid_arg);
    assert(shift_left<std::uint8_t>(3, 5) == 96);
    assert(shift_left<std::uint32_t>(1, 31).exception == shift_result_exception::none);
}

How to avoid bitwise operations outside the width of the data type in c++

2 Answers2