Как сделать неопределенный битовый сдвиг "правильным"

Question

В C ++ битовый сдвиг n -битного целого числа на n является неопределенным поведением:

std::uint64_t v = 1;
v = v << 64; // Undefined behaviour
std::cout << v << std::endl;

Приведенный выше код печатает 1 на моей машине. «Правильный» результат такого битового сдвига должен быть 0, и наивным решением будет использование ветки:

std::uint64_t v = 1;
std::uint64_t offset = 64;
v = offset >= 64 ? 0 : v << offset;
std::cout << v << std::endl;

Есть ли способ получить тот же результат без использования ветки?

Answer 1

Да.

Мы хотим исправить ситуацию, чтобы, если offset больше или равно 64, результат был равен нулю.

Стратегия:

1. Сдвиг вправо на 6 бит, назовите это temp.
2. Если temp равно нулю, мы хотим инициализировать маску для всех 1 бит, в противном случае для всех 0 бит. Мы можем достичь sh этого, установив mask = !!temp - 1.
3. Теперь просто побитовое и v и offset с mask.

Реализация:

uint64_t shift(uint64_t value, uint64_t offset) {
    uint64_t temp = offset >> 6;
    uint64_t mask = (!!temp) - 1;
    return (value & mask) << (offset & mask);
}

Вместо смещения offset вы также можете просто побитовое - и это с ~0x3F, вероятно, будет быстрее.

uint64_t shift(uint64_t value, uint64_t offset) {
    uint64_t mask = (!!(offset & ~0x3F)) - 1;
    return (value & mask) << (offset & mask);
}