Compute interval for a node in a binary tree

Question

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 >>= 1)
    {
        ++r;
    }

    return r;
}

void Interval(int i, int min, int max, int & a, int & b)
{
    auto d = Log2i(i);      // Depth of node i.
    auto k = 1 << 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;
}

Answer 1

It may depend on your application, but this could be somewhat simplified. If we note that there are twice as many nodes on each level, it sounds a lot like binary. Here's a table showing the node number (in hex), the binary representation of 1+node number and then the corresponding interval. Each level is separated by a blank line.

0 0001 1000 2000

1 0010 1000 1500 
2 0011 1500 2000 

3 0100 1000 1250 
4 0101 1250 1500 
5 0110 1500 1750 
6 0111 1750 2000 

7 1000 1000 1125
8 1001 1125 1250
9 1010 1250 1375
a 1011 1375 1500
b 1100 1500 1625
c 1101 1625 1750
d 1111 1750 1875

This suggests a very simple method:

void Interval(int i, int min, int max, int &a, int &b) 
{
    int mask = 8;  
    // find highest set bit
    for (++i; (i & mask) == 0; mask >>= 1)
    { }
    b = (max-min) / mask;  // calculate interval
    a = min + (i  - mask) * b; // calculate start
    b += a; // end = start + interval
}

Here's test code:

#include <cassert>

void testrange(int i, int mya, int myb)
{
    int min = 1000;
    int max = 2000;
    int a, b;
    Interval(i, min, max, a, b);
    assert(a == mya);
    assert(b == myb);
}


int main()
{
    testrange(0x0, 1000, 2000);
    testrange(0x1, 1000, 1500);
    testrange(0x2, 1500, 2000);
    testrange(0x3, 1000, 1250);
    testrange(0x4, 1250, 1500);
    testrange(0x5, 1500, 1750);
    testrange(0x6, 1750, 2000);
    testrange(0x7, 1000, 1125);
    testrange(0x8, 1125, 1250);
    testrange(0x9, 1250, 1375);
    testrange(0xa, 1375, 1500);
    testrange(0xb, 1500, 1625);
    testrange(0xc, 1625, 1750);
    testrange(0xd, 1750, 1875);
}

Note that I've started with the mask equal to 8, but it could be set to any arbitrarily useful single bit that is large enough for your table. That is, if nodes = the number of nodes in the tree, either mask | nodes == mask or mask > nodes.

Answer 2

Not sure if it is much smarter, but

p = s / k;

could be replaced by

p = s >> 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 >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);

    return x & ~(x >> 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