Optimal way to perform a shift operation on an array

Suppose I have an array

unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9};

Is there a way to perform shift operation on them besides just copying them all into another array. We can easily do it u开发者_运维百科sing linked lists but I was wondering if we can use a shift operator and get work done faster.

Note: The data in this question is just an example. The answer should be irrecpective of the data in the array.

If you want a circular shift of the elements:

std::rotate(&arr[0], &arr[1], &arr[10]);

... will do the trick. You'll need to #include the algorithm header.

As long as the array is modifiable, you can use memmove to shift them (but don't mistakenly use memcpy as memcpy is not meant for overlapping regions):

memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr));

(sizeof(arr) - sizeof(*arr) is the size in bytes of all but 1 element of the array).

If you're the only person with a pointer to the array, just increment the pointer and decrement the length.

Just remember to keep the original pointer around for when you free it.

If you're looking for a pure C solution, here it is, including a driver program. It turns out to be pretty simple: to rotate by n, you:

1. reverse the first n elements in-place,
2. reverse the remaining elements in-place, and
3. reverse the whole array in-place.

This requires one element worth of extra storage (for reversing).

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

/* print an array */
static void print_array(unsigned char *arr, size_t n, const char *prefix)
{
    size_t i;

    if (prefix) {
        printf("%s: ", prefix);
    }
    for (i=0; i < n; ++i) {
        printf("%02x ", (unsigned int)arr[i]);
    }
    printf("\n");
}

/* reverse 'arr', which has 'narr' elements */
static void reverse(unsigned char *arr, size_t narr)
{
    size_t i;

    for (i=0; i < narr / 2; ++i) {
        unsigned char tmp = arr[i];
        arr[i] = arr[narr-i-1];
        arr[narr-i-1] = tmp;
    }
}

/* rotate 'arr' of size 'narr' by 'shift' */
static void rotate(unsigned char *arr, size_t narr, unsigned long shift)
{
    reverse(arr, shift);
    reverse(arr + shift, narr - shift);
    reverse(arr, narr);
}

/* driver program */
int main(int argc, char *argv[])
{
    unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9,10};
    size_t narr = sizeof arr / sizeof arr[0];
    unsigned long shift = 2;

    if (argc > 1) {
        char *eptr;
        shift = strtoul(argv[1], &eptr, 0);
        if (*eptr || errno == ERANGE) {
            perror("strtoul");
            return EXIT_FAILURE;
        }
    }
    print_array(arr, narr, "before shift");
    rotate(arr, narr, shift);
    print_array(arr, narr, "after shift");
    return EXIT_SUCCESS;
}

If you really want BLAZING speed look at the assembler shift with carry operations. http://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate#Shift_With_Carry_Instructions Coupled with a loop you can bitshift an array in milliseconds.

I wonder if perhaps you should be using a std::valarray.