12

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?

justin
  • 104,054
  • 14
  • 179
  • 226
P i
  • 29,020
  • 36
  • 159
  • 267
  • 1
    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. – Mitch Wheat Sep 19 '10 at 02:37
  • 2
    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! – P i Sep 19 '10 at 02:52
  • 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. – Jens Gustedt Sep 19 '10 at 07:32
  • 10
    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. – P i Sep 19 '10 at 11:47
  • I've posted an answer for an efficient library [http://stackoverflow.com/questions/2633400/c-c-efficient-bit-array/10442966#10442966][1] Alf [1]: http://stackoverflow.com/questions/2633400/c-c-efficient-bit-array/10442966#10442966 – alf May 04 '12 at 05:58

5 Answers5

17

see CFMutableBitVector/CFBitVector for a CFType option

justin
  • 104,054
  • 14
  • 179
  • 226
  • 2
    http://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBitVectorRef/Reference/reference.html – JeremyP Sep 20 '10 at 13:00
  • But those classes store CFBit objects, which are typedeffed to 32 bit ints. So this solution wastes just as much memory. – pseudosudo Mar 26 '11 at 01:24
  • 8
    @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. – justin Apr 02 '11 at 05:17
11

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.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
  • 1
    And replace the 8's with `CHAR_BIT` if you care about complete portability to any C environment. – R.. GitHub STOP HELPING ICE Sep 19 '10 at 16:54
  • 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... – R.. GitHub STOP HELPING ICE Sep 19 '10 at 17:24
  • 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)))))` – easeout Jan 12 '13 at 20:51
6

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.

asveikau
  • 39,039
  • 2
  • 53
  • 68
  • 1
    The question isn't tagged C++. Perhaps you should convert your code to C. – JeremyP Sep 20 '10 at 12:58
  • 2
    @JeremyP - 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. – asveikau Sep 20 '10 at 20:40
  • 4
    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. – JeremyP Sep 21 '10 at 08:26
2
#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)))))
marcas
  • 21
  • 1
0

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
Frank C.
  • 7,758
  • 4
  • 35
  • 45