Efficient bitshifting an array of int?

Question

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.

@nn - its a little unclear what you're after here. What do you want to do with any of the data that is shifted and lost? Do you wish to logically shift or arithmetically shift data? Or are you just after reading a selection of binary data bits at random? For example read a 4 byte int from position bit 27 to bit 59 from a 100 byte binary data stream? — ChrisBD
– ChrisBD, Commented May 5, 2010 at 14:17
@ChrisBD: Sorry good question. Logically shift. I'm actually manipulating big integers represented as an array of ints, where each int corresponds to a digit in base 2^(sizeof(int)*8)=2^32. — snap
– snap, Commented May 5, 2010 at 14:26
I've been looking a few bit wizzardry references and I haven't seen any trick for this, I guess the obvious way is the only way :-/ — fortran
– fortran, Commented May 5, 2010 at 14:37

2 revs · Accepted Answer · 2017-03-05 14:31:25Z

9

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-2] = arr[len-1] << 1;
    arr[len-1] = 0;
}

edited Mar 5, 2017 at 14:31

community wiki

2 revs
Mark Ransom

Sign up to request clarification or add additional context in comments.

4 Comments

snap Over a year ago

Could you clarify where to start shifting? You say start shifting to the left using the highest order int. However in your code snippet it appears that you're shifting beginning from the lowest order int. Also on the shift left by one, what does the (& 1) indicate? Thanks.

Mark Ransom Over a year ago

Sorry, I went big-endian on you. You're right, the array order is backwards. The &1 masks off a single bit; to get 2 bits would be &3, 4 bits would be &0xf, 7 bits would be &0x3f etc.

snap Over a year ago

Er sorry, I meant to say, what does masking off the bit signify? Is it saying, after the shift, mask off the bits that matter, i.e. (32-1) bits?

Matt Wolfe Over a year ago

I don't think the shift by 33 works because lets say length = 4, in the for loop you first set arr[0], then arr[1], at which point i = 4 - 2, so we never set arr[2] to anything, and then arr[3] gets 0'd out.

p8me · Accepted Answer · 2017-11-03 16:47:18Z

For anyone else, this is a more generic version of Mark Ransom's answer above for any number of bits and any type of array:

/* This function shifts an array of byte of size len by shft number of
bits to the left. Assumes array is big endian. */

#define ARR_TYPE uint8_t

void ShiftLeft(ARR_TYPE * arr_out, ARR_TYPE * arr_in, int arr_len, int shft)
{
    const int int_n_bits = sizeof(ARR_TYPE) * 8;
    int msb_shifts = shft % int_n_bits;
    int lsb_shifts = int_n_bits - msb_shifts;
    int byte_shft = shft / int_n_bits;
    int last_byt = arr_len - byte_shft - 1;
    for (int i = 0;  i < arr_len;  i++){
        if (i <= last_byt){
            int msb_idx = i + byte_shft;
            arr_out[i] = arr_in[msb_idx] << msb_shifts;
            if (i != last_byt)
                arr_out[i] |= arr_in[msb_idx + 1] >> lsb_shifts;
        }
        else arr_out[i] = 0;
    }
}

Fernando Miguélez · Accepted Answer · 2010-05-05 14:35:00Z

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, ...)

answered May 5, 2010 at 14:35

community wiki

Fernando Miguélez

Collectives™ on Stack Overflow

Efficient bitshifting an array of int?

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related