Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C
Tip/Trick

BitArray in C

Rate me:
Please Sign up or sign in to vote.
2.78/5 (6 votes)
20 Jan 2010CPOL1 min read 61.8K   6   3
Introduction...
Introduction


Recently I got a task to implement a complex algorithm which involves lot of bitwise operation .After a bit struggle, I found a simple solution in C.
BitArray Structure


The easy and efficient way to store the bit information of a value is to create a structure as follows
//Structure to hold a single bit

typedef struct {
unsigned int bit : 1;
} Bit;

//BitArray structure.

typedef struct {
Bit bitValues[BIT_ARRAY_LENGTH];
} BitArray; 

nth bit of an integer


Here is the algorithm to findout the nth bit of an integer

nthBit of X =

1) Perform logical AND between X and 1
2) Right shift the result from step 1 n times

For example to findout the 3rd (4th position) bit of 171 (10101011)

tmp = 171 & (1 << 3)
result = tmp >> 3

The following function shows how to do this.

//Return the requested bit value of an integer
Bit getBit(int value, int position)
{
Bit singleBit;
singleBit.bit = 0;

if(position == 0) {
singleBit.bit = value & 1;
}else {
singleBit.bit = ( value & (1 << position ) ) >> position;

}
return singleBit;
}


Integer value from the bit array


We often require to convert back the bit array into the integer value. The following function does that.

//gets the value of BitArray
int getValue(BitArray bitArray)
{
int value = 0;
unsigned int bitValue = 0;

bitValue = bitArray.bitValues[0].bit;
value |= bitValue;
for(int i = 1; i < BIT_ARRAY_LENGTH; i++)
{
bitValue = bitArray.bitValues[i].bit;
bitValue <<= i;
value |= bitValue;
}

return value;

} 

Example of Usage


Imagine that we have to find out a secret key from a given value and the algorithm is as follows

->3rd bit of the value = 2nd bit of value XOR 3rd bit of value
->2nd bit of the value = 3rd bit of value XOR 1st bit of value
->1st bit of the value = 4th bit of value XOR 2nd bit of value

The following function shows how to do this by using our bitArray functions.
C++
int calculateKey(int value) {
   unsigned int key = 0;
   BitArray bitArray = getBitArray(value);
   bitArray.bitValues[3].bit = bitArray.bitValues[2].bit 
                              ^ bitArray.bitValues[3].bit;
   bitArray.bitValues[2].bit = bitArray.bitValues[3].bit 
                              ^ bitArray.bitValues[1].bit;
   bitArray.bitValues[1].bit = bitArray.bitValues[4].bit 
                              ^ bitArray.bitValues[2].bit;
   
   key = getValue(bitArray);
   return key;
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
India India
Jafar is working in software field for the last five years. He is from Moonniyoor, a village of north Kerala,India.
Visit Jafar's home page http://jafarmlp.googlepages.com/

Comments and Discussions

 
GeneralReason for my vote of 1 no doc that this would pack the stru... Pin
Member 806903230-Sep-11 0:43
Member 806903230-Sep-11 0:43 
GeneralReason for my vote of 2 That's NOT a bit array Pin
gbb216-Feb-11 11:44
gbb216-Feb-11 11:44 
Reason for my vote of 2
That's NOT a bit array
GeneralThat is NOT bit array Pin
gbb216-Feb-11 11:43
gbb216-Feb-11 11:43 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.