12,446,525 members (53,880 online)
Tip/Trick
alternative version

35.8K views
5 bookmarked
Posted

BitArray in C

, 20 Jan 2010 CPOL
 Rate this:
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.
```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;
}```

Share

 Software Developer (Senior) India
Jafar is working in software field for the last five years. He is from Moonniyoor, a village of north Kerala,India.

You may also be interested in...

 Pro Pro

 First Prev Next
 Reason for my vote of 1 no doc that this would pack the stru... Member 806903230-Sep-11 0:43 Member 8069032 30-Sep-11 0:43
 Reason for my vote of 1 no doc that this would pack the struct into a real bit array, and hence a lot of overhead for what could be done with a simple enum
 Reason for my vote of 2 That's NOT a bit array gbb216-Feb-11 11:44 gbb21 6-Feb-11 11:44
 That is NOT bit array gbb216-Feb-11 11:43 gbb21 6-Feb-11 11:43
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Aug-16 18:13 Refresh 1