c++ - 转移大数字

Question

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

除了有什么快速的方法吗？~~X << 8~~ X << 591~~X * 2^8~~ X * 2^591

score 2 · Accepted Answer

任意位数的位移都非常容易。只需记住将溢出的位移动到下一个元素。就这样

下面是一个左移 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 ⁵⁹¹。如果您想像二进制一样转换，您必须更改为2 的幂的基数，例如基数 2 ³²或基数 2 ⁶⁴

一个通用的解决方案是这样的，四肢存储在 little-endian 中，每个数字都在 base 2 ^{CHAR_BIT*sizeof(T)}

template<typename T>
void rshift(std::vector<T>& x, std::size_t shf_amount) // x >>= shf_amount
{
    constexpr std::size_t width = CHAR_BIT*sizeof(T);
    if (shf_amount > width)
        throw;

    const std::size_t shift     = shf_amount % width;
    const std::size_t limbshift = shf_amount / width;
    
    std::size_t i = 0;
    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;
    for (; i < x.size() ; ++i)
        x[i] = 0;
}

此外，从标签来看，您可能使用链表来存储肢体，由于元素分散在内存空间周围，它对缓存不友好，并且由于下一个指针，它也浪费了大量内存。事实上，你不应该在大多数现实生活中的问题中使用链表

score 0 · Accepted Answer

我认为，如果您使用 64 位整数，则代码应该是

    o3 = i3 << 3 | i2 >> (32 - 3);
    .....

c++ - 转移大数字

2 回答 2

编辑：

Related

Reference