Searching for an algorithm to find n bits in a bitte

Call the machine word size w (often w = 32 or 64) and the total number of memory pages 4 KB m. If there are g spaces between the blocks already allocated, and there is some free block of length-n that fits completely into the machine word (and you are happy with the choice of the smallest such block, and not one that crosses the border between two words), then its can be found in O (m / w + g) time , using the method wraps around the addition of "ripples":

• Given a bitmap word representing w 4KB pages, invert all of its bits. Now any block of k consecutive free 4KB pages is a block of k consecutive 1-bits.
• If you add an integer whose only 1-bit is the LSB of that block, the carries will pulsate completely, leaving all k bits in that block at 0 and the next bit at 1.

Using this alone, it is not too hard to find a space that contains n bits in O (m / w + g), without using expensive or "weird" instructions like multiply, divide, or scan bits. But in order to find the smallest such block, you seem to need either a bit scan or a split. Fortunately, we can limit the number of times we need to use these instructions for no more than w-1 operations in total over the entire bitmap, since this is the largest number of times the best break in that area can be "closed" to less, (Instead of using subdivision, you can use code like the last paragraph to find the MSB index in O (logs w) time using simple instructions, this might be faster, but the point is moot.since so few subdivisions are required.) We still need O (g) multiplications, which may not be perfect, but are fast on modern CPUs.

const int m = /* HOW MANY BLOCKS */;
const int w = sizeof (unsigned) * CHAR_BIT;
unsigned bits[m / w];

unsigned findSmallestBlock(unsigned n) {
    if (n > w) return UINT_MAX;    // Can only find within-word blocks.
    unsigned bestI = UINT_MAX;    // Index with bits[]
    unsigned bestLsb = 0;  // Has a 1-bit in the LSB of the gap; 0 = "no solution"
    unsigned bestShifted = ~0;    // The gap bits, "flush right".
    for (int i = 0; i < sizeof bits / sizeof bits[0]; ++i) {
        // Find the shortest block in bits[i], if one exists
        // First, handle an edge case
        if (bestLsb == 0 && bits[i] == 0) {
            // We don't handle this edge case
            bestI = i;
            bestLsb = 1;
            bestShifted = ~0;
            if (n == w) break;    // Perfectly snug
        }
        unsigned y = ~bits[i];
        unsigned probe = y & (y - 1);    // The LSB of the gap we will test
        while (probe << (n - 1)) {    // Left-shifting it too far => 0 => stop.
            y += probe;    // Ripple!
            unsigned edge = y & (y - 1);    // Extract new LSB.  Overflow to 0 OK.
            unsigned gap = edge - probe;    // Every bit in the gap is 1.
            // Is the gap big enough?
            if (probe << (n - 1) <= gap) {
                // The gap is big enough.  Is it the tightest fit so far?
                // Doing this with bit-scan operations is easy; without them we can
                // use integer multiplication and division, but we want to keep the
                // divisions to a minimum.  Needs an edge case to be handled above.
                if (gap < bestShifted * probe) {
                    // Found a new, shorter gap.
                    // The division shifts the entire block right so that it starts
                    // at bit 0.  It expensive, but happens at most w-1 times.
                    bestI = i;
                    bestLsb = probe;
                    bestShifted = gap / probe;
                    // Is it perfectly snug?  If so, we can stop now.
                    if (probe << (n - 1) > gap >> 1) goto done;    // Yes, "goto".
                }
            }
            y -= edge;            // Clear the *new* LSB; ignore intervening bits
            probe = edge << 1;    // Again, skip over all intervening bits
        }
    }

done:
    if (bestLsb == 0) return UINT_MAX;    // Didn't find anything

    // Find the index of the 1-bit in bestLsb in O(log w) time.
    unsigned pos = bestI * w;
    unsigned z = w >> 1;    // The number of bits we will try to shift right
    while (bestLsb > 1) {
        unsigned x = bestLsb >> z;
        if (x) {
            bestLsb = x;
            pos += z;
        }
        z >>= 1;
    }

    return pos;
}

      

        
        
        
      

    

A word about time complexity: O (m / w + g) is the same as O (m) time that some other solutions suggest when g is about the same size as m, which can happen: for example if every second page is 4KB was distributed, then g = m / 2. But if g is small - either because there aren't many pages allocated, or because almost all of them have, or because they were just allocated and deallocated in the pattern, resulting in a few whitespaces - then the time complexity is closer to O (m / w).

One more thing: without changing the time complexity, this code can be adapted to find blocks that span word boundaries by tracking the final break in each word and doing a one-off test at the beginning of each word to see if the previous word grows, the final break will work. It is also possible to search for blocks larger than w (otherwise: any space that satisfies the query for n> kw pages must contain at least k full words of 0 values ​​in the [] bits - using this can significantly reduce the constant coefficient when searching for large spaces). Both of these extensions require more accounting.