circular byte shifting in an array

Question

I'm coding an LED display (7x48) and the language I'm working in is BASIC (no former experience in that language, but in C/C++) and I have a small issue. I have an array (red[20] of byte) and an example of a current state is: to make it easier here lets say its red[3]

10011010 01011100 01011101

and now i need to shift the array by 1 so in next cycle its supposed to be

00110100 10111000 10111011

so what happened is that the whole array shifted for 1 bit to left

the BASIC I'm working with doesn't have any .NET APIs so I need the total low level code (doesn't have to be BASIC, I can translate it, I just need an idea how to do it as I'm limited to 8KB code memory so I have to fully optmize it)

Answer 1

You should be able to use bit shift operations: http://msdn.microsoft.com/en-us/library/2d9yb87a.aspx

Let x be the element you want to shift:

x = (x<<1) | (x>>23)

or in general, if you want to shift left by y bits and there are a total of n bits:

x = (x<<y) | (x>>(n-y))

I don't know basic well, but here's what I would do in a C++/Java/C# language:

Assuming you have red[] of length n:

int b = 32; //Number of bits per byte (your example showed 24, but usually there are 32)
int y = 1; //Number of bytes to shift to the left
int carry = 0;  //The bytes to carry over (I'm assuming that they move up the array from red[0] to red[1], etc.

for (int i=0;i<n;i++)
{
    int newCarry = (red[i]>>(n-y));
    red[i] = (red[i]<<y) | carry;
    carry = newCarry;
}

//Complete the loop
red[0]|=carry;

Answer 2

If most significant bit is 1:
    subtract value of most significant bit
    multiply by 2 
    add 1
otherwise:
    multiply by 2