Инвертирование порядка битов в 64‑разрядном беззнаковом числе

Условие

Дано значение типа uint64_t. Требуется построить и вернуть новое число того же типа, в котором биты исходного значения расположены в противоположном порядке – первый бит становится последним, второй – предпоследним и так далее.

Ответ

Последовательно переносите младший бит входа в накапливаемый результат, сдвигая результат влево. Нужно выполнить ровно 64 шага, включая ведущие нули исходного числа.

#include <cstdint>

std::uint64_t reverseBits(std::uint64_t value) {
    std::uint64_t result = 0;
    for (int i = 0; i < 64; ++i) {
        result = (result << 1) | (value & 1ULL);
        value >>= 1;
    }
    return result;
}

Беззнаковый тип делает сдвиги определёнными; величина каждого сдвига равна единице. Для входа 1 получится число с установленным старшим битом, для 0 — 0. Для фиксированного uint64_t затраты постоянны; в общем случае это O(w) по числу битов.