X = 712360810625491574981234007851998使用链表表示,每个节点都是unsigned int
c++ - 转移大数字-LMLPHP

除了X << 8 X << 591以外,还有其他快速方法可以执行X * 2^8 X * 2^591吗?

最佳答案

任意数量的位移位都很容易。只需记住将溢出的位移至下一个元素。就这样
下面是左移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;
与向右移动相似,只是在相反方向上迭代。
编辑:
似乎您使用的是以109为底的作为您的大数字,因此二进制移位而不是适用于此处。在基数B中向左/向右移动N个数字等效于将数字分别乘以BN和B-N。您不能以十进制进行二进制移位,反之亦然
如果不更改基数,则只有一个解决方案,那就是将数字乘以2591。如果要像二进制那样进行移位,则必须更改为base that is a power of 2,例如基数232或基数264
一个通用的解决方案是这样的,将肢体存储在little-endian中,并且每个数字都以2CHAR_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;
}
此外,在标签中,您可能使用链接列表来存储肢体,由于元素散布在整个存储空间中,因此不适合缓存,并且由于下一个指针的使用,它还会浪费大量内存。实际上,在大多数现实生活中的问题中,您都不应该使用链表
  • 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
  • 10-04 20:24