Determinig Array index when given arrayan Element without using loops; array elements follow a set pattern where next element is twice the current element

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...

Open in new window


I would like to directly determine the index of an element. For example if I have
512

Open in new window

I would output index
1

Open in new window

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

Open in new window


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?
Henry KorirSoftware EngineerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Florian LenschowCommented:
If your pattern really always consists of base2 exponentials (2,4,8 ...) you could use the logarithm
 log(number)/log(2)

Open in new window

In C the log is natural so you need to convert it to base 2. Then you substract the log result from the current array length, since you store them in descending order. This however depends on the value your array ends on and you might need to adjust to get the correct index. But may I ask why you need this array? Couldn't a function of n that returns the power 2^n achieve what you want to do?
0
sarabandeCommented:
if your pattern really always consists of base2 exponentials (2,4,8 ...)

that doesn't matter. the only important thing is that the next item is the half of the previous item.

then (array[0] / number) necessarily is a multiple of 2's only.

int bitpos(unsigned char b)
{
     int bit = 0;
     if (b != 0) 
     {
       switch(b)
       {
         case 1<<0: bit = 1;  break;
         case 1<<1: bit = 2;  break;
         case 1<<2: bit = 3;  break;
         case 1<<3: bit = 4;  break;
         case 1<<4: bit = 5;  break;
         case 1<<5: bit = 6;  break;
         case 1<<6: bit = 7;  break;
         case 1<<7: bit = 8;  break;
        }
    }  
    return bit;
}

int index_in_half_series(int start, int find)
{
    unsigned int n = start/find;

    unsigned char b0 = bitpos((unsigned char)(n & 0xff));      
    unsigned char b1 = bitpos((unsigned char)((n>>8) & 0xff));
    unsigned char b2 = bitpos((unsigned char)((n>>16) & 0xff));
    unsigned char b3 = bitpos((unsigned char)((n>>24) & 0xff));
    int index = b0? (b0 - 1) : b1? (7+b1) : b2?(15+b2) : (23+b3);
    return index;
}

int main()                              
{                                        
    int array1[] = {1024,512,256,128,64,32,16,8,4,2,1};
    int number1  = 16;
    int index1   = index_in_half_series(array1[0], number1);

    int array2[] = { 737, 368, 184, 92 };
    int number2  = 92;
    int index2   = index_in_half_series(array2[0], number2);
    return 0;
 }  

Open in new window


Sara
1

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Henry KorirSoftware EngineerAuthor Commented:
The solution works well and I have a shortcut:
index=logb2((array[0])/size);
where logb2() is a function to find log to base 2, array[0] is the first element in the array and it is the largest value in the array (the array is arranged in descending order), and size is the value which it's index in the array is being determined.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
arrays

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.