Determinig array index of a particular element without using looping

Question

Suppose the length of array is dynamic and the elements follow the same pattern where by the next element is half the previous element. For example 1024, 512, 256, 128...

I would like to directly determine the index of an element. For example if I have 512 I would output index 1 without looping through the elements and comparing them with 512 then output 1. i.e not like this:

for (int i = 0;  i < length;  ++i) {
    if (array[i] == 512) { 
        printf("%d\n", i);
        break;
    }
}

I have been thinking of using modulus or bit manipulation like shifts but I can't get it to work. How can this be achieved?

There's no direct way to do this. In general, you would have to construct an auxiliary index, perhaps a hash table. (In your case, since the numbers in the array seem to follow a pattern, I guess you could compute the position using base-2 logarithms, but that's obviously a very special case. But see @tkausl 's comment if that's what you want.) — Steve Summit, Apr 24 '18 at 15:20
It's not possible to do that without examining the individual elements of the array, until the required value is found. In general, that involves a loop, but for four elements, a loop can be unrolled. Modulus or bit manipulation might be used to examine individual elements, but not to loop over them, — Peter, Apr 24 '18 at 15:23
@K1b1w077 I bet using `log2()` is slower than my formula :) and it could be even slower than lookup in 4 elements array — Slava, Apr 24 '18 at 15:39
Suppose the length of the array is dynamic and the elements follow the same pattern where by the next element is twice the previous element. For example 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768... — henrykorir, Apr 24 '18 at 15:47
@K1b1w077 you say "I have an array of 4 elements" how am I suppose to read your mind? — Slava, Apr 24 '18 at 15:49
@K1b1w077 I have rephrased my answer and pointed to generic solution. — Slava, Apr 24 '18 at 17:04

Abhishek Keshri · Accepted Answer · 2018-04-24T15:33:35.003

3

The elements of your array are: 1024 512 256 128. They all are power of 2, so taking log2 of each element will give:

10, 9, 8, 7

So you can do something like:

if array[i]==n
        print 10-log2(n)

This solution is valid only for your given pre-defined array.

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

int main(void) {
    int a[4] = {1024, 512, 256, 128};
    for(size_t i=0;i<4;i++)
        printf("%d %d\n",a[i],10-(int)log2(a[i]));
    return 0;
}

Output:

edited Apr 24 '18 at 15:33

answered Apr 24 '18 at 15:26

Abhishek Keshri

3,074
14
31

You might even have a compiler built-in for finding the highest set bit in a number, which could be used in place of `log2` (for speed at the cost of portability). And you can prove the input is a power of 2 by testing `n & (n-1)` is zero. – Toby Speight Apr 24 '18 at 16:11
The answer surely works with the arrays of elements 128, 256, 512, 1024. Suppose the length of the array is dynamic and the elements follow the same pattern where by the next element is twice the previous element. For example 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768... – henrykorir Apr 24 '18 at 16:16
1

it follows the same pattern, you can find it using `log2` – Abhishek Keshri Apr 24 '18 at 16:19

Slava · Answer 2 · 2018-04-24T15:52:30.200

0

If you are sure that given value is correct (ie you do not need to validate), this should work:

3 - ( n >> 8 ) + ( n >> 10 )

live example

Another alternative is using 3 conditions (but only 2 are always exectuted), but that most probably would be slower due to branch predictions:

n > 512 ? ( n < 1024 ? 1 : 0 ) : ( n > 128 ? 2 : 3 )

if your array can be arbitrary size use method from this question Find the highest order bit in C

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

just subtract result from proper number.

edited Apr 24 '18 at 15:52

answered Apr 24 '18 at 15:31

Slava

43,454
1
47
90

What if the length of the array is dynamic and the elements follow the same pattern where by the next element is twice the previous element. For example 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768... – henrykorir Apr 24 '18 at 15:46
1

@K1b1w077 what if you ask your questions correctly? – Slava Apr 24 '18 at 15:47

henrykorir · Answer 3 · 2018-04-25T06:13:14.977

The solution 10-log2(n), where n is an array element which needs its index determined, gave me an insight. I was struggling to figure out what 10 meant in the 10-log2(n). I realized the general solution is log2(X)-log(n) where X is the largest known element in the array. The array should be sorted in descending order such that the 0th element the largest

EXAMPLE:

Array[5]={2048, 1024, 512, 256, 128};

To find the index of array element 256 will be log2(2048)-log2(256)=11-8=3 Therefore the general solution is log2(largest array element)-log2(base2 value you are looking for) and you MUST know the largest array element AND the array is assumed to be sorted in descending order Live example here

BEST OPTION:index=log2(array[0]/value) where value is the array element to determine its index index=log2(array[0]/value) live example here

Determinig array index of a particular element without using looping

3 Answers3