Search code examples
cbit-manipulationbitmapdata

How to check if a set of bits are 0 from a determinated position?

I'm writting a bitmap physical memory manager and i want implement a function that checks if a n bits are free starting from an specific bit. Right now I use this function that checks if a single bit is free and i call it n times to see if n bits are free but i think it is not very efficient to do it this way:

inline static bool physical_memory_map_test(uint32_t bit)
{
    return physical_memory.blocks[bit/32] & (1 << bit % 32);
}

So I want to implemnt something like this: (the "" contains pseudo code):

static bool physical_memory_map_test(uint32_t starting_bit, uint32_t count)
{
    int excess = (starting_bit%32 + count) -32;
    if(excess < 0)
        return (physical_memory.blocks[bit/32] & "-excess number of 1s" << bit % 32)) && (physical_memory.blocks[bit/32] & "count + excess number of 1s" << bit % 32));

    return physical_memory.blocks[bit/32] & ("count number of ones, if count is 3, this should be 111" << bit % 32); 
}

Or something better to check if all the bits are 0 (return true) or if at least one of them is a 1(return false) How could i do that?

Solution

  • Since you are checking a range of uint32_t words, you will end up with a loop. Your task is to make it loop by 32 bits instead of looping by 1 bit.

    You need to check partial 32-bit words at both ends:

    Bit groups

    In order to do that you need to construct a mask with k lower bits set to 1, and upper (32-k) set to 0. You can do it like this:

    uint32_t mask_K = ~(~0U << k);

    Use

    if (block & mask_K)

    to test the lower k bits;

    if (block & ~mask_K)

    tests the upper k bits.