Gregory Hildstrom Projects Publications Resume Links Contact About Google+ Facebook Youtube Donate




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;
}