How to find out the degree of a number, which is the arithmetic mean of the powers of two numbers?

Question

Algorithms

In the task, you need to reduce the number of comparisons when adding an element to the binary heap to log (log (n)), for this you need to use a bean. Search. I figured out the algorithm itself, but I can’t figure out how best to calculate the indices.

For example, a new element is added at index 18 (the heap is minimum oriented),

the array contains the following values

a[18] = 1.5
a[9] = 9
a[4] = 2.5
a[2] = 2
a[1] = 1

I need to compare a[4] and a[18]. The power of 4 is the average of the powers of 2 in 1 and 18 (rounded down). How can you find out this degree?

Answer 1

Strange task. What is the use of this reduction in comparisons, if the total result of the insertion will move up to O(log n) elements?
But, if necessary, then for each number you first need to find out the number of the most significant non-zero bit (most significat bit - MSB), and then shift the top number to the right by half the difference in the positions of the most significant bits.
1 = 000000 1 b, msb = 0
18 = 00 1 0010b, msb = 4 Difference
- 4 digits. So, you need to shift 2 bits to the right:
18 >> 2= 00100 10 b >> 2 = 00100b = 4
Another example: for 4 and 18 msb there would be 2 and 4, the difference is -2. Shifting 18 2/2=1 digit to the right would give you 9.
In order for this optimization to give at least some benefit, you need to find msb very quickly. Either precalculate them for all possible indices, or hope your language has a built-in function that calls the desired processor instruction, such as __builtin_clz .
You can also calculate msb only once for the right border of the binsearch, and then just remember it, because the middle point has the arithmetic mean (the left border is initially 1 - it has msb = 0). And then, in the process of binsearch, you just need to store msb for two boundaries and replace one of the ends with a known value of the middle.
To pre-calculate, just loop through msb[i] = msb[i/2] + 1;