packed bits
This short C program demonstrates how to efficiently pack large numbers of bits into an array of multi-byte integer elements. This strategy is useful when storage space or bandwidth are at a premium or when multi-byte comparisons and assignments are performed far more often than single-bit manipulations. However, the single-bit manipulation overhead may be a performance problem when that operation is performed frequently.
#include< stdio.h >
#include< stdint.h >
#define totalbits 1024 //even multiple of packsize
#define packsize 32 //sizeof(uint32_t)*8, power of 2
#define shift 5 //2^5 = 32
#define mask 31 //32-1
uint32_t packedbitarray[totalbits/packsize];
void setbit(uint32_t packedbits[], uint32_t bitnumber, uint8_t bitvalue){
uint32_t arrayoffset = bitnumber >> shift;
uint32_t bitoffset = bitnumber & mask;
uint32_t flipbit = 1 << bitoffset;
packedbits[arrayoffset] = (packedbits[arrayoffset] | flipbit) ^ flipbit;
packedbits[arrayoffset] |= bitvalue << bitoffset;
}
uint8_t getbit(uint32_t packedbits[], uint32_t bitnumber){
return (packedbits[bitnumber>>shift] >> (bitnumber&mask)) & 0x1;
}
int main(int argc,char** argv){
int i;
//initialize bits to zero one at a time (slow single-bit manipulation)
for(i=0;i < totalbits;i++){
setbit(packedbitarray,i,0);
}
//initialize bits to zero 32 at a time (faster multi-bit manipulation)
for(i=0;i < totalbits/packsize;i++){
packedbitarray[i] = (uint32_t)0;
}
//set a single bit to show it works
setbit(packedbitarray,5,1);
//print bits 0-9 to show it works
printf("bits[0-9]: ");
for(i=0;i < 10;i++){
printf("%u",getbit(packedbitarray,i));
}
printf("\n");
return 0;
}
unpacked bits
This short C program demonstrates how to store large numbers of bits unpacked into an array of uint8_t (unsigned char) elements. This strategy is useful when single-bit manipulation performance is critical. However, storage space may be a concern. Bit comparisons and assignments can be sped up by treating groups of 4 bits as 32-bit integers and subsequently using integer operations.
#include< stdio.h >
#include< stdint.h >
#define totalbits 1024 //number of bits and number of elements in storage array
int bitratio = sizeof(uint32_t)/sizeof(uint8_t); //for handling groups of 4 unpacked bits as packed into an integer
uint8_t unpackedbitarray[totalbits];
int main(int argc,char** argv){
int i;
//initialize bits to zero one at a time (fast single-bit manipulation)
for(i=0;i < totalbits;i++){
unpackedbitarray[i] = 0;
}
//initialize bits to zero 4 at a time (faster multi-bit manipulation)
for(i=0;i < totalbits/bitratio;i++){
((uint32_t*)(unpackedbitarray))[i] = (uint32_t)0;
}
//set a single bit to show it works
unpackedbitarray[5] = 1;
//print bits 0-9 to show it works
printf("bits[0-9]: ");
for(i=0;i < 10;i++){
printf("%u",unpackedbitarray[i]);
}
printf("\n");
return 0;
}
