Compute interval for a node in a binary tree Given a binary tree organised as in the diagram below (a static tree represented by an array of 15 nodes), I am writing code to compute the interval represented by a given node at index i, given the interval of the entire tree (node 0)?  My motivation to do this is to get rid of the need to store the interval in a node instance.



Here's my stab at computing the value.  It appears to be correct but I'm wondering if there's a much smarter way of calculating it:

int Log2i(int x)
{
    auto r = 0;

    while (x &gt;&gt;= 1)
    {
        ++r;
    }

    return r;
}

void Interval(int i, int min, int max, int &amp; a, int &amp; b)
{
    auto d = Log2i(i);      // Depth of node i.
    auto k = 1 &lt;&lt; d;        // At this level, there are k intervals.
    auto s = max - min;     // Total span over which we're partitioned.
    auto p = s / k;         // Therefore, size of each interval.
    auto f = k - 1;         // Index of first node for this partition.

    a = min + (p * (i - f));    
    b = a + p;
}

int main(void)
{
    auto a = int(), b = int();

    Interval(6, 1000, 2000, a, b);

    return 0;
}
Not sure if it is much smarter, but

p = s / k;


could be replaced by

p = s &gt;&gt; d;


, which removes a division, and might produce faster code.

Instead of using the Log2 function, you may get better performance with such a function for computing k directly:

uint32_t msb32(uint32_t x)
{
    x |= (x &gt;&gt; 1);
    x |= (x &gt;&gt; 2);
    x |= (x &gt;&gt; 4);
    x |= (x &gt;&gt; 8);
    x |= (x &gt;&gt; 16);

    return x &amp; ~(x &gt;&gt; 1);
}


source: http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

See also: https://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i