Fast formula to get the range a number is in, given a perfect binary subdivision?

Question

Mind the set of positive integers from 0 til L exclusive. For any positive integer n up to log2(K), can split the set in 2^n consecutive subsets of equal length. For example, for L = 256, n = 3, we'd get 2^3, or 8, subsets: {0..31}, {32..63}, {64..95}, {96..127}, {128..160}, {160..191}, {192..223}, {224..255}.

Let f(L,n,i) : Nat -> Nat -> Nat -> (Nat,Nat) return, given an arbitrary L and n, the subset that some i is contained in. For example, for f(256,3,100) = (96,127), because, if we divide the 0..255 range in 2^3 subsets, then number 100 is contained in the subset ranging from 96 to 127.

My question is, what is a fast implementation of f? I wonder if it is possible to do so in constant time, with just a few bitwise operations.

Answer 1

Quite obviously, just compute the length of each subset (l), divide i by l, and take the floor k. The desired range goes from l*k to l*(k+1)-1. In JavaScript:

function subrange_of_i(L, n, i) {
  var l = L / (2 ** n); // or just `L >>> n`
  var k = Math.floor(i / l);
  return [l*k, l*(k+1)-1];
};

(TODO: convert to C for the sake of this answer.)

Answer 2

This works:

#include <stdio.h>

typedef struct { int a, b; } pair;

pair f(int L, int n, int i) {
    int len = L / (1 << n);
    int a = i / len * len;
    return (pair) { a, a + len - 1 };
}

int main() {
    pair p = f(256, 3, 100);
    printf("%d %d\n", p.a, p.b);
}

I am not good with floating point, but looping works as expected:

#include <stdio.h>
#include <math.h>

typedef struct { double a, b; } paird;

paird fd(double L, double n, double i) {
    double len = L / pow(2, n);
    double a = 0, b;
    while (b = a + len, b < i) {
        a = b;
    }
    return (paird){ a, b };
}

int main() {
    paird p = fd(127, 7, 100);
    printf("%f %f\n", p.a, p.b); // (99.218750, 100.210938)
}