Effective bitdrive array int?

Question

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

Given an array of integers, what would be an effective method for logical bitwise shifting the array left or right?

I am considering a helper variable, such as long, that will calculate the bit-shift for the first pair of elements (index 0 and 1) and set the first element (0). Continuing in this way the bitrate for the elements (index 1 and 2), there will be a computer, and then index 1 will be set.

I think this is actually a pretty effective method, but there are drawbacks. I can not beat more than 32 bits. I think using a few helper variables will work, but I foresee recursion somewhere along the line.

Answer 1

There is no need to use long as an intermediary. If you move left, start with the highest order int, moving the right start from the lowest level. Add to the hyphen from an adjacent element before changing 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 method can be extended to shift more than 1 bit. If you make more than 32 bits, you take the number of bits 32 and shift it by moving the result further along the array. For example, to shift left by 33 bits, the code would look something like this:

 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; } 

Answer 2

Check out the BigInteger implementation in Java , which internally stores data as an array of bytes. In particular, you can check the leftShift () function. The syntax is the same as in C, so it would not be so difficult to write a couple of such functions. Also keep in mind that when it comes to bit offsets, you can use advanced types in C. This means that in Java, to safely transfer data without the clutter of a sign, you usually need larger types for storing data (i.e., Int to shift is short, long to shift int, ...)

Answer 3

For anyone, this is a more general version. Mark the Ransom 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; } }