Any way to check if a bool** pointer to pointer contains a true value in C without loops?

Question

I am trying to optimise an iOS app and just wanted some advice on an issue I am having.

I have a bool** which can hold up to 1024 * 1024 elements. Each element defaults to false but they can also be changed to true at random.

I wanted to know if there is a streamlined way to check if a true value is contained by any of the elements, as, in a worst case scenario over a million iterations would be needed to do this check using two loops.

I could be completely wrong but I had thought about casting the memory to an int, in the belief that, as a false value is equal to 0, if all the elements are false then the result of casting it to an int would, I had thought, be 0. This is not the case however.

What I may have to go with is to keep a tally of the number of true values as they are toggled but this could turn quite messy very quickly.

I hope I have made myself clear enough without code but, if you need to see any code, just ask.

--Edit-- So I decided to go with mvp's answer. Then when I need to check if a certain bit is set:

uint32_t mask32_t[] = {
    0x01, 0x02, 0x04, 0x08,
    0x10, 0x20, 0x40, 0x80,
    0x100, 0x200, 0x400, 0x800,
    0x1000, 0x2000, 0x4000, 0x8000,
    0x10000, 0x20000, 0x40000, 0x80000,
    0x100000, 0x200000, 0x400000, 0x800000,
    0x1000000, 0x2000000, 0x4000000, 0x8000000,
    0x10000000, 0x20000000, 0x40000000, 0x80000000
};

bool bitIsSet(uint32_t word, int n) {
    return ( word & mask32_t[ n ] ) != 0x00;
}

bool isSetAtPoint( uint32_t** arr, int x, int y ) {
    return bitIsSet( arr[ (int)floor(x / 32.0) ] [ y ], x % 32 );
}

Answer 1

Probably best optimization you can make is to convert your 1024x1024 array of booleans into array of bits. This approach has some benefits and drawbacks:

1. + Bit array will consume 8 times less memory: 1024*1024/8 = 128KB.
2. + You can quickly test many bits at once by checking 32-bit integers quickly. In other words, finding first non-zero bit can be 32-times as fast.
3. - You need to create custom routines to read and write bits in this array. However, this is rather simple task - just a bit of bit twiddling :).

Answer 2

Basically, the answer is no. You need to write a loop to check.

You cannot cast a composite value to an int. You don't report a compiler error, so I suspect you actually tried casting the pointer to your array to int, which is legal; however, the result will only be 0 if the pointer is NULL (that is, not pointing to anything.)

You can streamline the checking code by using a bitvector instead of an array of bools. (You'd also save quite a bit of memory.) However, that involves a lot more code, and it's fairly messy. If you were using C++, you would have access to std::bitset, which is a lot easier than writing your own, but has the disadvantage of needing a compile-time size.