Extracting the Last N Bits from an Array of Bytes in C

Question

I have an array of unsigned characters in C:

unsigned char array[] = { 0xF0, 0xCC, 0xAA, 0xF0}; 
/* Represented as binary: 11110000 11001100 10101010 11110000 */

I'd like to extract the last N bits from this array and store them in an integer. For instance, if I want to extract the last 5 bits, the result should be:

int i = 32; /* Represented as binary: 10000 */

I tried using the BIGNUM library, but I found it to be overkill and a bit slow for this purpose. Is there a more efficient way to achieve this in C?

code attached:

unsigned char array[] = { 0xF0, 0xCC, 0xAA, 0xF0}; 
int i = 0; 
int j;
int totalBits = sizeof(array) * 8;  
int startBit = totalBits - 5;  

for (j = startBit; j < totalBits; j++) 
{
            i = i << 1;
            i = i | (array[j] & 1);
}    

Answer 1

Valiant effort! Thank you for showing your attempt.

I've added a few comments to your version:

unsigned char array[] = { 0xF0, 0xCC, 0xAA, 0xF0}; 
int i = 0; 
int j;
int totalBits = sizeof(array) * 8;  // currently meaning 32
int startBit = totalBits - 5;  // meaning 27 where '5' is the magic number wanted

for (j = startBit; j < totalBits; j++) 
{
            i = i << 1;
            i = i | (array[j] & 1); // Oops! there is no array[27]! Top element is array[3]!
}    

Below is a rough draft of a version that seems to work:

int main(void) {
    unsigned char arr[] = { 0xF0, 0xCC, 0xAA, 0xF0 }; // Your array (add more! Try it out!)

    union { // providing for up to N = 64bits (on my system)
        unsigned char c[8];
        unsigned long l;
    } foo;

    foo.l = 0; // initialise

    size_t sz = sizeof arr / sizeof arr[0]; // source byte count
    size_t n = 0; // destination byte count

    // wastefully copy as many bytes as are available until 'foo' is a full as possible
    // Notice the 'endian-ness' of index n going from 0 to 8.
    // Other hardware could change this to count downward, instead.
    for( size_t i = sz; i && n < sizeof foo; ) {
        foo.c[ n++ ] = arr[ --i ]; // grab one byte
        printf( "%x\n", foo.l ); // debugging
    }

    int N = 5;
    foo.l &= (1<<N)-1; // Mask off the low order N bits from that long

    printf( "%x\n", foo.l );

    return 0;
}

Hope this helps.

Late caveat: maximum value of N, in this code, is 63... One should add checking that N doesn't exceed the width of the accumulator foo, and if N is exactly that number, bypass the shift-and-mask operation...

PS: When playing with bit manipulation, it's often safer to used unsigned datatypes. Some C implementations apparently object to the sign bit being fiddled inappropriately.