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?

Conlon

have you tried searching to see if someone has written something you can use? People aren't going to just write your code for you. – Brinkman

I was actually trying to share some code I had written by asking a question and answering it, but this site is so fast!!! within the 10 minutes it has taken me to assemble my answer, already two answers have appeared! – Conlon

SO is not meant to post questions that you can answer yourself. And even then you might consider looking on what exists on the subject on the web and compare your approach to what you find, first. – Curch

Respectfully, if you read the first few lines of the FAQ, it says 'Please look around to see if your question has already been asked (and maybe even answered!) before you ask. It's also perfectly fine to ask and answer your own question, as long as you pretend you're on Jeopardy: phrase it in the form of a question.' I checked that this topic has not yet been covered on SO, and posted because I think my code could help people. – Conlon

I've posted an answer for an efficient library [https://mcmap.net/q/433836/-c-c-efficient-bit-array/… Alf [1]: https://mcmap.net/q/433836/-c-c-efficient-bit-array/… – Carolinian

Answer 1

see CFMutableBitVector/CFBitVector for a CFType option

Burleson

developer.apple.com/library/mac/#documentation/CoreFoundation/… – Mclemore

But those classes store CFBit objects, which are typedeffed to 32 bit ints. So this solution wastes just as much memory. – Timmie

@whitman the values are passed as CFBit; that doesn't mean they are stored as such. i just looked at the implementation of CFBitVector (r.550.13). memory consumption is one bit, while allocations sizes are rounded up to a number divisible by 64. a very conservative implementation overall. – Burleson

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.

Galloglass

And replace the 8's with CHAR_BIT if you care about complete portability to any C environment. – Galloglass

Actually, 8 works just fine anywhere if you don't mind wasting bits on platforms where CHAR_BIT>8, and it will give better performance than introducing things like division by 9 or 10... – Galloglass

To support the clear operation &=~ which is two operators, &= and ~, you need to wrap the latter half of the macro in another set of parens. Otherwise you write something you don't mean to. #define BITOP(a, b, op) ((a) [(size_t) (b) / (8 * sizeof *(a))] op ((size_t) 1 << ((size_t) (b) % (8 * sizeof *(a))))) – Arrester

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.

Ciao

The question isn't tagged C++. Perhaps you should convert your code to C. – Mclemore

@Mclemore - It was an illustrative example anyway. I decided to use references instead of pointers because I thought it would distract less from the question being asked. I think the point got across OK, and the answer wasn't meant to be copy-pasted into someone's solution anyway. – Ciao

the question is about C. The questioner might not even know what a reference is. If that's the case, you haven't distracted less, you have distracted more. – Mclemore

Answer 4

#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)))))

Enzyme

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

Nitrosamine