c++ 向量中 long long int 的位移，例如 380 位

Question

我正在寻找一种有效的方法来按位移动 long long int 的整个向量。应该移动整个向量，而不仅仅是分别移动每个值。移位值可以是随机的，例如向右移位 380 或 2000 位。在 C++ 中有没有一种有效的方法来做到这一点？

void bitwiseRightShiftFunction(std::vector<uint64_t>& values, uint64_t shiftValue){ ?? values = values >> shiftValue;}

Answer 1

以下代码对

uint64_t

的向量进行就地、按位、右移，假设最后一个向量元素在右边，即最不重要。这是一个直接但高效的实现。可以在 GitHub 存储库 cpp-core/so.

中找到此代码和一个简单的驱动程序

功能：

#include "core/util/tool.h"
#include "core/util/random.h"

// Shift the bits in `a` by `n` bits to the right (towards lesser
// signifigance assuming that a[0] is the most significant word)
// prepending with zero bits as necessary.
void right_shift(std::vector<uint64_t>& a, size_t n) {
    constexpr auto bits_per_word = sizeof(uint64_t) * CHAR_BIT;

    // Parition n into the number of a number of whole words to shift and the
    // remaining number of bits to shift.
    auto words_to_shift = n / bits_per_word;
    auto bits_to_shift = n % bits_per_word;

    // Create a bit mask that covers the upper `bits_to_shift`
    // bits in a word. The value `(uint64_t{1} << bits_to_shift) -
    // 1` is the lower `bits_to_shift` bits so the bit reversal
    // turns them into the upper `bits_to_shift` bits.
    auto mask = __builtin_bitreverse64((uint64_t{1} << bits_to_shift) - 1);

    // The words in range [0,limit) are the only bits that will appear
    // in the result because words in range [limit,a.size) are shifted
    // "off the end". Starting with the least significant word, loop
    // over all the words that will contribute bits to the result
    // (possibly none).
    for (int src_idx = a.size() - words_to_shift - 1; src_idx >= 0; --src_idx) {
        // In general this source word will be split between the two
        // destination words left and right (least significant). The
        // lower `bits_to_shift` bits will go to the upper bits of the
        // right word while the upper bits will become the lower bits
        // of the left word.
        auto rdx = src_idx + words_to_shift + 1;
        auto ldx = src_idx + words_to_shift;

        // Get the source value and rotate it `bits_to_shift` bits to
        // the right so that the bits are aligned with their
        // eventual destinations.
        auto value = __builtin_rotateright64(a[src_idx], bits_to_shift);

        if (rdx < a.size())
            a[rdx] |= value bitand mask;
        a[ldx] = value bitand ~mask;
    }

    // Prepend with zeros as necessary
    for (auto i = 0; i < words_to_shift; ++i)
        a[i] = 0;
}

测试程序：

int tool_main(int argc, const char *argv[]) {
    ArgParse opts
        (
         argValue<'n'>("number-bits", 512, "Number bits"),
         argValue<'m'>("shift", 380, "Right shift M bits"),
         argFlag<'v'>("verbose", "Verbose diagnostics")
         );
    opts.parse(argc, argv);
    auto n = opts.get<'n'>();
    auto m = opts.get<'m'>();
    // auto verbose = opts.get<'v'>();

    std::vector<uint64_t> bits(1 + n / 64);
    std::uniform_int_distribution<uint64_t> d;
    for (auto& value : bits)
        value = d(core::rng());

    cout << std::string(m, ' ');
    for (const auto& value : bits)
        cout << fmt::format("{:064b}", value);
    cout << endl;

    right_shift(bits, m);
    for (const auto& value : bits)
        cout << fmt::format("{:064b}", value);
    cout << endl;

    return 0;
}

结果：

$ make right_shift && right_shift -n 64 -m 17
.................11010000100100011011101101011100001000101010111010011110111101101110011111100001111110101110111011010101110000110001111101111001
00000000000000000110100001001000110111011010111000010001010101110100111101111011011100111111000011111101011101110110101011100001