Click here to Skip to main content
11,637,415 members (64,439 online)
Click here to Skip to main content

Tagged as

BitArray in C

, 20 Jan 2010 CPOL 30.5K 5
Rate this:
Please Sign up or sign in to vote.
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;
}

License

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

Share

About the Author

jafarmlp
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/

You may also be interested in...

Comments and Discussions

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

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150728.1 | Last Updated 20 Jan 2010
Article Copyright 2010 by jafarmlp
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid