Shift N bits an entire array of chars

问题:

Let's say I have an array of chars and I want to shift N bits to the left each byte, carrying to the left, so only the N bits of the first character would be lost.

Example: kxmo shifted 3 bits to the left should become X@hx

This is what I have currently, but it's not working as expected:

#include <stdio.h>

int main(void) {
    //shift the array with length *len* *shift* bits to the left
    int len = 4, shift = 3;
    unsigned char a[len] = "kxmo";
    unsigned char b[len]; //X@hx

    unsigned char tmp = 0, tmp2 = 0;
    for(int i = len - 1; i > 0; i--) {
        tmp = 0 | (a[i] << shift);
        b[i] = a[i];

        tmp2 = 0 | (a[i - 1] << shift);
        b[i - 1] = (a[i - 1] << shift) ^ tmp;
    }

    printf("old: %s | new: %s\n", a, b);

    return 0;
}

Where am I failing?

Edit:

This is what I'm getting right now: old: kxmo | new: �xmo

回答1:

First, imagine doing it with pencil and paper. Let's say you are shifting two bytes by three bits, you start with bytes abcdefgh, ijklmnop, and you want to finish with defghijk, lmnop000.

In order to do this, you need to extract 00000ijk from the second byte, and OR it into the first byte after the shift. In order to do this, you need to shift the second byte by 8-shift to the right, and mask the result with 00000111 i.e. the last shift bits set to 1. This mask can be constructed by shifting 1 to the left shift+1 times, yielding 00001000, and subtracting 1 from the result.

Here is how you can do it:

char b1 = 'k';
char b2 = 'x';
int shift = 3;
int carry = 0, nextCarry;

nextCarry = (b1 >> (8-shift)) & ((1<<(shift+1))-1);
b1 <<= shift;
b1 |= carry;
carry = nextCarry;

Now do the same with b2:

nextCarry = (b2 >> (8-shift)) & ((1<<(shift+1))-1);
b2 <<= shift;
b2 |= carry;
carry = nextCarry;

If you do this in a loop, you would achieve the desired result.

Demo.

回答2:

How about something like that (assuming 0 <= shift < 8):

#define BITS_IN_BYTE 8
for(int i = len - 1; i > 0; i--) 
{
    b[i] = a[i] << shift;
    b[i - 1] = (a[i - 1] << shift) | (a[i] >> (BITS_IN_BYTE - shift));
}

I didn't check it but I hope it will do what you want.

EDIT

OK, I checked and it does what you expect.

NOTE --> you need to set len to 5 and not to 4 for '\0'. also note that the first iteration (b[i] = a[i] << shift;) will be done on the '\0' but since its value is 0, it is OK.