Get the bit which is most at the left with dichotomy

user_13960223 0
Viewed 64

I'm trying to understand how this following code works and I am not able to understand what happens here:

uint32_t mask[5] = { 0xFFFF0000, 0xFF00, 0xF0, 0b1100, 0b10 };
uint32_t shift[5] = { 16, 8, 4, 2, 1 };

char first_bit_left_dichotomy(uint32_t M) {
    char pos = 0;
    char i;
    for (i = 0; i <= 4; i++) {
        if (M & mask[i]) { 
            M = M >> shift[i]; 
            pos += shift[i]; 
        }
    }
    return pos;
}

Indeed, I have two questions please, first of all: if it was a size comparison shouldn't the mask be created in this order?

uint32_t mask[5] = { 0b100, 0b1100, 0xF0, 0xFF00, 0xFFFF0000 };

Thus, what does the program in the for loop please? With my research I understand & and >> and their bitwise behaviours, but what's the trick here because I guess it only and only compares with mask[0] since it's necessary the same size.

bit bit-shift bit-manipulation c
1 Answers

The algorithm follows the "divide and conquer" principle by applying a binary search on or bit pattern to figure out what the most significant bit is.

It basically halves the machine word with every cycle. The beauty of this is, that you always calculate MSB within 5 steps, regardless what 32 bit pattern you put in as the binary search has O(log2(n)) characteristics.

Let's pick two extremes to illustrate the behaviour and assume the word 0x00000001 as an input to the algorithm. We would expect it to output 0. What basically happens is:

0x00000001 & 0xFFFF0000 = 0x00000000
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0xFF00 = 0x0000
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0xF0 = 0x00
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0b1100 = 0x00
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0b10 = 0b0
-> We don't shift anything, M=0x00000001, pos=0

So we got our result within 5 steps. Imagine now doing a loop from left to right attempting the same thing: It would take 31 steps to get to the result.

Also the word 0x8FFFFFFF as an input to the algorithm would need 5 steps to get the expected result 31:

0x8FFFFFFF & 0xFFFF0000 = 0x8FFF0000
-> We shift by 16 right, M=0x8FFF, pos=16

0x8FFF & 0xFF00 = 0x8F00
-> We shift by 8 right, M=0x8F, pos=24

0x8F & 0xF0 = 0x80
-> We shift by 4 right, M=0x8, pos=28

0x8 & 0b1100 = 0x8
-> We shift by 2 right, M=0x2, pos=30

0x2 & 0b10 = 0x2
-> We shift by 1 right, M=0x1, pos=31

As you can see, both extremes took us exactly those 5 steps. Thanks to loop unrolling, conditional execution of instructions, etc. this is supposed to run quite fast, at least by far faster than looking for the MSB set from left to right in a loop.

user_18630810
Related