Most efficient way to find the bit with 0 in an array of uint32_t

Question

I am having an array of type uint32_t say of size 1024.

int32_t *handle_generator= calloc(1024, sizeof(uint32_t));

I am going to use this array handle_generator to generate handle for elements of certain type - myType_t. When an element of myType_t is created, I have to find the first bit from the array handle_generator which is zero and return that index value. And I am going to use this value as handle for my newly created element.

The created element of type myType_t can be destroyed as well. In that case, the handle values of that destroyed element becomes free and can be reused. So the index in the array handle_generator (matching that handle value) should be set to 0.

After multiple creation and deletion of elements myType_t there will series of 0s and 1s bits in the array handle_generator. In such a condition, what is the efficient way to find the first bit with value 0?

Simplest way is to loop through the array handle_generator by inspecting each bit, which would have a time complexity of 0(n); where n is the number of bits.

---

For example, after many additions and deletion, if the bits in the handle_generator array is as below

 0th                       13th
 |                         |
 v                         v
+-------------------------------------------------------------------------+
|1|1|1|1|1|1|1|1|1|1|1|1|1|0|1|1|1|1|1|1|1|1|1|1|1|0|1|1|1|1|1|1|...|0|0|0|
+-------------------------------------------------------------------------+

If we have to find the first bit in the array - handle_generator, having value 0, then it is at index 13. So what is most efficient algorithm to figure this out?

Answer 1

You have 1024 words to make a bit-mask of 32768 bits.

In addition to this, I would use 32 words to make a bit-mask indicating which of those 1024 words are full or non-full, and then a single word to make a bit mask of which of those 32 words are full.

That's only an additional 33 words, but with that you can find the first 0 very quickly -- use the top-level mask to find the first non-full mid-level mask, use the mid-level mask to find the first non-full word, and then find the first 0 in that word.

Of course, doing this quickly requires a quick way to find the index of the least significant bit that is set or cleared in a word. That's a common topic: Position of least significant bit that is set