Таблица поиска ключей вида k = 2^n с размером массива n

Я хочу сделать справочную таблицу/массив.

Значения индекса, которые я получаю, имеют форму k = 2^n только, где n — целое число. Итак, я хочу уменьшить размер массива до n, и поэтому мне также нужно выполнить операцию со значениями индекса.

Мне нужен наиболее эффективный способ сделать это, поскольку я программирую на встроенной платформе.

Пример:

Я получил значения n = {1, 2, 4, 8, 16, 32}

У меня есть массив, определенный как:

int myArray[6];

Теперь я хочу преобразовать значения n в m, где m = {1, 2, 3, 4, 5, 6}, чтобы я мог получить доступ к элементам массива:

myArray[m];

c lookup-tables
person uniquenamehere    schedule 19.12.2014    source источник
comment
Как насчет хэш-карты?   -  person Rerito    schedule 19.12.2014
comment
дубликат stackoverflow.com/q/53161/812912   -  person Ivaylo Strandjev    schedule 19.12.2014
comment
@Rerito, вероятно, не лучшее решение для встроенной системы. В зависимости от процессора вы можете найти старший бит целого числа с помощью вызова сборки (BSR для i86). Затем вы просто используете это для значения поиска.   -  person IdeaHat    schedule 19.12.2014
comment
@IdeaHat Ах да, я неправильно понял вопрос и упустил суть   -  person Rerito    schedule 19.12.2014
comment
Самый быстрый портативный способ конвертации — поиск по таблице.   -  person chux - Reinstate Monica    schedule 19.12.2014
comment
@IvayloStrandjev: Как уже отвеченный вопрос ответил на мой вопрос?   -  person uniquenamehere    schedule 19.12.2014
comment
@Phataas, ваши проблемы точно такие же - вам нужно вычислить старший бит числа. Конечно, вы не сможете скопировать код и просто решить с его помощью свою проблему, но он нуждается в очевидных изменениях.   -  person Ivaylo Strandjev    schedule 19.12.2014
comment
Я хочу каким-то образом преобразовать 2 ^ n в n без использования логарифмов. Какой связанный ответ находит старший бит? Мои значения уже могут быть ТОЛЬКО 2 ^ n, где n - целое число, поэтому нет смысла искать старший бит.   -  person uniquenamehere    schedule 19.12.2014

Ответы (1)


arrow_upward
1
arrow_downward

Это решение

#include <stdio.h>

int main()
{
    int array[6] = {1, 2, 4, 8, 16, 32};
    int index[6];
    int i;

    for (i = 0 ; i < 6 ; i++)
    {
        int value;

        value    = array[i];
        index[i] = 0;
        while ((value >>= 1) != 0)
            index[i] += 1;
        printf("%d\n", index[i]);
    }
    return 0;
}
person Iharob Al Asimi    schedule 19.12.2014
comment
array[i] >> i == 1 для любых входных данных, поскольку они представляют собой совершенную степень двойки. Предположим теперь, что мы вводим пробел (типа {2, 4, 8, 16, 32, 64}, тогда это даст {2, 3, 4, 5, 6, 7}, а 7 - недопустимый индекс... - person Rerito; 19.12.2014
comment
Разве цель не состоит в том, чтобы извлечь log(.) каждого входа (конечно, логарифм базы 2)? - person Rerito; 19.12.2014
comment
Я думаю ты прав. Я неправильно понял вопрос. - person Iharob Al Asimi; 19.12.2014