转移大数字 [英] Shifting big numbers

问题描述

X = 712360810625491574981234007851998使用链接列表表示，并且每个节点都是unsigned int

X = 712360810625491574981234007851998 is represented using a linked list and each node is an unsigned int

除了 X * 2^8 X * 2^591之外，是否还有一种快速的方法来执行 X << 8 X << 591?

Is there a fast way to do X << 8 X << 591 other than X * 2^8 X * 2^591 ?

推荐答案

在任意数量的位中，移位都是非常容易的.只要记住将溢出的位移到下一个元素即可.就这样

Bit shifting is very easy in any arbitrary number of bits. Just remember to shift the overflowed bits to the next element. That's all

下面是左移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;

类似于右移，只是在相反的方向上迭代.

Similar for shifting right, just iterate in the reverse direction.

您似乎使用10以10为底的数字(sup> 9 )，因此二进制移位不适用于 . 转移"基数B中的左/右N位数字分别等于将数字分别乘以B ^N 和B ^-N .您不能用十进制进行二进制移位，反之亦然

It seems that you're using base 10⁹ for your large number, so binary shifting does not apply here. "Shifting" left/right N digits in a base B is equivalent to multiplying the number by B^N and B^-N respectively. You can't do binary shift in decimal and vice versa

如果不更改基准，则只有一个解决方案，那就是将数字乘以2 ⁵⁹¹ .如果要像二进制那样转换，则必须更改为 2的幂的基数，例如基数2 ³² 或基数2 ⁶⁴

If you don't change your base then you have only one solution, that's multiplying the number by 2⁵⁹¹. If you want to shift like in binary you must change to a base that is a power of 2 like base 2³² or base 2⁶⁴

一般的解决方案是这样的，将肢体存储在little-endian中，并且每个数字都以2为底 ^{CHAR_BIT * sizeof(T)}

A general solution would be like this, with the limbs stored in little-endian and each digit is in 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;
}

此外，在标签中，您可能会使用链接列表来存储肢体，由于元素散布在整个内存空间中，因此不便于缓存，并且由于，它还会浪费大量内存下一个指针.实际上，在大多数现实生活中的问题中，您都不应该使用链表

Moreover from the tag you're likely using a linked-list for storing the limbs which is not cache-friendly due to elements scattering all around the memory space, and it also wastes a lot of memory due to the next pointers. In fact you shouldn't use linked list in most real life problems

• Bjarne Stroustrup说我们必须避免链接列表
• 数字处理:为什么永远不应该再在代码中再次使用链接列表
• Bjarne Stroustrup:为什么应该避免链接列表
• 列表中有邪恶吗?—Bjarne Stroustrup

• 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

这篇关于转移大数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！