Lookup table for keys that are of the form k = 2^n with array size of n

Question

I want to make a lookup-table/array.

The index values I get are of the form k = 2^n only, where n is an integer. So I want to reduce the arrays size to n and I therefore have to perform an operation on the index values as well.

I want the most efficient way to do this as I am programming on an embedded platform.

Example:

I got the values n = {1, 2, 4, 8, 16, 32}

I have an array defined as:

int myArray[6];

Now I want to convert the values n to m, where m = {1, 2, 3, 4, 5, 6} so I can access array elements:

myArray[m];

@Rerito probably not a great solution on a embedded system. Depending on the processor you can find the most significant bit of a integer with an assembly call (BSR for i86). Then you just use that for the lookup value. — IdeaHat, Dec 19 '14 at 15:19
@IdeaHat Oh right, I misunderstood the question and missed the point — Rerito, Dec 19 '14 at 15:20
@IvayloStrandjev: How did the "already answered question" answer my question? — uniquenamehere, Dec 19 '14 at 16:06
@Phataas your problems is precisely the same - you need to compute the highest order bit of a number. Of course you will not be able to copy paste the code and just solve your problem with it but it needs obvious modifications — Ivaylo Strandjev, Dec 19 '14 at 16:09
I want some way to convert from 2^n to n without using logarithms. What the linked answer do it find the highest bit? My values can already ONLY be 2^n where n is an integer, so no point in finding highest bit.. — uniquenamehere, Dec 19 '14 at 16:11

Iharob Al Asimi · Answer 1 · 2015-01-02T14:50:24.400

1

This is a solution

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

edited Jan 02 '15 at 14:50

answered Dec 19 '14 at 15:16

Iharob Al Asimi

52,653
6
59
97

`array[i] >> i == 1` for any input since they are perfect power of two. Suppose now that we introduce a gap (like `{2, 4, 8, 16, 32, 64}`, then this will yield to `{2, 3, 4, 5, 6, 7}`, and 7 is an invalid index ... – Rerito Dec 19 '14 at 15:21
Isn't the objective to extract the `log(.)` of each input (base 2 log of course) ? – Rerito Dec 19 '14 at 15:35
I think you're right. I understood the question the wrong way. – Iharob Al Asimi Dec 19 '14 at 15:37

Lookup table for keys that are of the form k = 2^n with array size of n

1 Answers1