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.
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments