Shifting big numbers

Question

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

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

Answer 1

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

Below is a left-shift-by-3 example

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.

Edit:

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

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⁶⁴

A general solution to shift would be like this, with the limbs ("digits" or each small word unit in a big integer, in arbitrary-precision arithmetic term) stored in little-endian and each digit is in base 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;
}

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. Actually the memory used by pointers and memory allocation is even larger than the memory for storing the data bits in this case. In fact you shouldn't use linked list in most real life problems

• 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

Answer 2

I think, if you use 64-bit integer the code should be

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