How do I implement a bit array in C / Objective C

Question

iOS / Objective-C: I have a large array of boolean values.

This is an inefficient way to store these values – at least eight bits are used for each element when only one is needed.

How can I optimise?

Answer 1

#define BITOP(a,b,op) \
   ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))

will not work ...

Fix:

#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))

Answer 2

Try this:

#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))

Then for any array of unsigned integer elements no larger than size_t, the BITOP macro can access the array as a bit array. For example:

unsigned char array[16] = {0};
BITOP(array, 40, |=); /* sets bit 40 */
BITOP(array, 41, ^=); /* toggles bit 41 */
if (BITOP(array, 42, &)) return 0; /* tests bit 42 */
BITOP(array, 43, &=~); /* clears bit 43 */

etc.

Answer 3

You use the bitwise logical operations and bit-shifting. (A Google search for these terms might give you some examples.)

Basically you declare an integer type (including int, char, etc.), then you "shift" integer values to the bit you want, then you do an OR or an AND with the integer.

Some quick illustrative examples (in C++):

inline bool bit_is_on(int bit_array, int bit_number)
{
   return ((bit_array) & (1 << bit_number)) ? true : false;
}

inline void set_bit(int &bit_array, int bit_number)
{
   bit_array |= (1 << bit_number);
}

inline void clear_bit(int &bit_array, int bit_number)
{
   bit_array &= ~(1 << bit_number);
}

Note that this provides "bit arrays" of constant size (sizeof(int) * 8 bits). Maybe that's OK for you, or maybe you will want to build something on top of this. (Or re-use whatever some library provides.)

This will use less memory than bool arrays... HOWEVER... The code the compiler generates to access these bits will be larger and slower. So unless you have a large number of objects that need to contain these bit arrays, it might have a net-negative impact on both speed and memory usage.

Answer 4

see CFMutableBitVector/CFBitVector for a CFType option

Answer 5

I came across this question as I am writing a bit array framework that is intent to manage large amounts of 'bits' similar to Java BitSet. I was looking to see if the name I decided on was in conflict with other Objective-C frameworks.

Anyway, I'm just starting this and am deciding whether to post it on SourceForge or other open source hosting sites.

Let me know if you are interested

Edit: I've created the project, called BitArray, on SourceForge. The source is in the SF SVN repository and I've also uploaded a compiled framework. This LINK will get your there.

• Frank