C++中对vector<uint64_t>整体按位右移任意位数的高效实现方法

C++标准库没有直接提供对std::vector<uint64_t>的整体按位右移函数，但可以实现一个高效的原地版本，核心思路是把大移位拆分成整64位块的移位和剩余不足64位的跨块移位两部分处理，避免逐个元素单独移位的冗余操作。

实现思路 #

1. 边界判断：如果移位位数大于等于vector所有元素的总位数（64 * size()），直接将所有元素置0，因为所有位都会被移出。
2. 拆分移位量：把shiftValue拆成两部分：
   • full_words = shiftValue / 64：表示需要整体右移多少个完整的uint64_t元素。
   • remainder_bits = shiftValue % 64：表示剩余不足64位的移位量，需要处理元素间的位传递。
3. 整块移位：用std::move将vector中从full_words索引开始的元素向前移动到起始位置，后面的位置填0，这一步是O(n)的高效操作。
4. 跨块移位：从vector末尾向前遍历，把每个元素的低remainder_bits位作为进位，传递给前一个元素的高位，同时将当前元素右移remainder_bits位，这一步确保不会覆盖未处理的元素，同样是O(n)复杂度。

代码实现 #

#include <vector>
#include <cstdint>
#include <algorithm>

void bitwiseRightShiftFunction(std::vector<uint64_t>& values, uint64_t shiftValue) {
    const size_t wordCount = values.size();
    if (wordCount == 0) return;

    constexpr uint64_t bitsPerWord = 64;
    const uint64_t totalBits = wordCount * bitsPerWord;
    if (shiftValue >= totalBits) {
        std::fill(values.begin(), values.end(), 0);
        return;
    }

    const uint64_t fullWords = shiftValue / bitsPerWord;
    const uint64_t remainderBits = shiftValue % bitsPerWord;

    // 处理整64位块的移位
    if (fullWords > 0) {
        std::move(values.begin() + fullWords, values.end(), values.begin());
        std::fill(values.end() - fullWords, values.end(), 0);
    }

    // 处理剩余不足64位的跨块移位，从后往前操作避免覆盖
    if (remainderBits > 0) {
        uint64_t carry = 0;
        for (auto it = values.rbegin(); it != values.rend(); ++it) {
            const uint64_t newCarry = *it << (bitsPerWord - remainderBits);
            *it = (*it >> remainderBits) | carry;
            carry = newCarry;
        }
    }
}

注意事项 #

• 上述代码假设vector的第一个元素是大整数的最高位，最后一个元素是最低位。如果你的存储顺序相反（第一个元素是最低位），只需将跨块移位的遍历方向改为从前往后即可。
• 该实现是原地操作，无需额外分配内存，时间复杂度为O(n)，在处理大vector时效率很高。

内容的提问来源于stack exchange，提问作者Miroslav Krajcir