Быстрая формула для получения диапазона, в котором находится число, с учетом идеального двоичного подразделения? - PullRequest
Новая
       3

Быстрая формула для получения диапазона, в котором находится число, с учетом идеального двоичного подразделения?

1 голос
/ 08 января 2020

Запомните набор натуральных чисел от 0 до L эксклюзив. Для любого натурального числа от n до log2(K) можно разбить набор на 2^n последовательных подмножеств равной длины. Например, для L = 256, n = 3 мы получили бы 2^3 или 8, подмножества: {0..31}, {32..63}, {64..95}, {96..127}, {128..160}, {160..191}, {192..223}, {224..255}.

Позвольте f(L,n,i) : Nat -> Nat -> Nat -> (Nat,Nat) вернуть, учитывая произвольные L и n, подмножество, в котором содержится некоторая i. Например, для f(256,3,100) = (96,127), потому что, если мы разделим 0..255 диапазон в 2^3 подмножествах, затем в подмножестве содержится число 100 в диапазоне от 96 до 127.

Мой вопрос: что такое быстрая реализация f? Интересно, возможно ли это сделать за постоянное время, всего лишь с помощью нескольких побитовых операций.

Ответы [ 2 ]

2 голосов
/ 08 января 2020

Это работает: 

#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);
}

Я не очень хорошо разбираюсь с плавающей запятой, но цикл работает, как и ожидалось: 

#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)
}
1 голос
/ 08 января 2020

Совершенно очевидно, просто вычислите длину каждого подмножества (l), разделите i на l и возьмите слово k. Требуемый диапазон варьируется от l*k до l*(k+1)-1. В 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: ради этого ответа преобразуйте в C.)

...