Efficient bitshifting an array of int?

Question

Hi,

To be on the same page, let's assume sizeof(int)=4 and sizeof(long)=8.

Given an array of integers, what would be an efficient method to logically bitshift the array to either the left or right?

I am contemplating an auxiliary variable such as a long, that will compute the bitshift for the first pair of elements (index 0 and 1) and set the first element (0). Continuing in this fashion the bitshift for elements (index 1 and 2) will be computer, and then index 1 will be set.

I think this is actually a fairly efficient method, but there are drawbacks. I cannot bitshift greater than 32 bits. I think using multiple auxiliary variables would work, but I'm envisioning recursion somewhere along the line.

Answer 1

Take a look at BigInteger implementation in Java, which internally stores data as an array of bytes. Specifically you can check out the funcion leftShift(). Syntax is the same as in C, so it wouldn't be too difficult to write a pair of funciontions like those. Take into account too, that when it comes to bit shifting you can take advange of unsinged types in C. This means that in Java to safely shift data without messing around with sign you usually need bigger types to hold data (i.e. an int to shift a short, a long to shift an int, ...)

Answer 2

There's no need to use a long as an intermediary. If you're shifting left, start with the highest order int, shifting right start at the lowest. Add in the carry from the adjacent element before you modify it.

void ShiftLeftByOne(int * arr, int len)
{
    int i;
    for (i = 0;  i < len - 1;  ++i)
    {
        arr[i] = (arr[i] << 1) | ((arr[i+1] >> 31) & 1);
    }
    arr[len-1] = arr[len-1] << 1;
}

This technique can be extended to do a shift of more than 1 bit. If you're doing more than 32 bits, you take the bit count mod 32 and shift by that, while moving the result further along in the array. For example, to shift left by 33 bits, the code will look nearly the same:

void ShiftLeftBy33(int * arr, int len)
{
    int i;
    for (i = 0;  i < len - 2;  ++i)
    {
        arr[i] = (arr[i+1] << 1) | ((arr[i+2] >> 31) & 1);
    }
    arr[len-1] = 0;
}