c++ - 转移大数字

Question

X = 712360810625491574981234007851998使用链表表示，每个节点是一个 unsigned int

有没有快速的方法来 X << 8 X << 591除了<罢工> X * 2^8 X * 2^591 ？

Answer 1

在任意数量的位中移位都非常容易。请记住将溢出的位移到下一个元素。就这样

下面是一个左移3的例子

uint64_t i1, i2, i3, o1, o2, o3; // {o3, o2, o1} = {i3, i2, i1} << 3;

o3 = i3 << 3 | i2 >> (32 - 3);
o2 = i2 << 3 | i1 >> (32 - 3);
o1 = i1 << 3;

类似右移，只是反方向迭代即可。

编辑:

似乎您使用的是基数 10⁹ 作为您的大数，因此二进制移位不适用于此。在基数 B 中“左/右移动”N 位数字相当于分别将数字乘以 B^N 和 B^-N。你不能对十进制进行二进制移位，反之亦然

如果你不改变你的基础，那么你只有一个解决方案，那就是将数字乘以 2⁵⁹¹。如果你想像二进制一样移位，你必须更改为 base that is a power of 2像基数 2³² 或基数 2⁶⁴

shift 的一般解决方案是这样的，limbs(“数字”或大整数中的每个小单词单元，在任意精度的算术项中)存储在 little -endian 并且每个数字都以 2 为基数 ^{CHAR_BIT*sizeof(T)}

template<typename T,
    class = typename std::enable_if<std::is_unsigned<T>::value>::type>
void rshift(std::vector<T>& x, std::size_t shf_amount) // x >>= shf_amount
{
    // The number of bits in each limb/digit
    constexpr std::size_t width = CHAR_BIT*sizeof(T);
    if (shf_amount > width)
        throw; // or zero out the whole vector for saturating shift

    // Number of limbs to shift
    const std::size_t limbshift = shf_amount / width;
    // Number of bits to shift in each limb
    const std::size_t shift     = shf_amount % width;
    
    std::size_t i = 0;
    // Shift the least significant bits
    for (; i < x.size() - limbshift - 1; ++i)
        x[i] = (x[i +     limbshift] >> shift) |
               (x[i + 1 + limbshift] << (width - shift));
    x[i] = x[i + limbshift] >> shift;
    i++;
    // Zero out the most significant bits
    for (; i < x.size() ; ++i)
        x[i] = 0;
}

此外，从标签来看，您可能使用链表来存储肢体，由于元素散落在内存空间周围，这对缓存不友好，而且由于，它还浪费了大量内存next 指针。实际上，在这种情况下，指针和内存分配使用的内存甚至比存储数据位的内存还要大。事实上，你不应该在大多数现实生活中的问题中使用链表

• Bjarne Stroustrup says we must avoid linked lists
• Why you should never, ever, EVER use linked-list in your code again
• Number crunching: Why you should never, ever, EVER use linked-list in your code again
• Bjarne Stroustrup: Why you should avoid Linked Lists
• Are lists evil?—Bjarne Stroustrup