Simple way of getting the nth array element when all I have is n^2

Question

I have an array of nine elements and an integer. Using the integer and bitmasking I want to save information about whether an element of the array is valid.

So my question is: Is there a simpler way than using log2() of math.h to get from my bitmask to my array element number? For example, I store foo2, foo4 and foo5 in mValue using bitmasking. Then I want to get the array element at position foo2 = 2, which is the second bit, so the 2nd array element, which is 34. But the only way I can think of is the log2(n) funtion. Is there a simpler one using bitshifting maybe?

Simply put, I want to do this:

Is the nth bit of an integer mValue set to 1? then get me the nth element of an array bar.

#include <math.h>  

const int  foo1 = 1;
const int  foo2 = 2;
const int  foo3 = 4;
const int  foo4 = 8;
const int  foo5 = 16;

int bar[9] = {23,34,82,8,7,0,23,19,20};
int mValue;

void SetValue(int nVal)
{
 mValue = nVal; 
}

bool IsElementValid(int nVal)
{
 return mValue & nVal;
}

int main()
{
 SetValue(foo2 | foo4 | foo5 );
 IsElementValid(foo4); //true
 IsElementValid(foo5); //true
 IsElementValid(foo1); //false

 //access array element 1 with value foo2 (2)
 if(IsElementValid(foo2))
    printf("%d\n",     bar[log2(foo2)]); // output: '34'
}

[this question and answers](http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set) might be useful for you — mvidelgauz, Jul 11 '16 at 15:27

AnoE · Answer 1 · 2016-07-11T15:14:15.850

2

The usual idiom is:

if (mValue & (1<<n)) {
  return bar[n];
}

EDIT: But if the only thing you have truly is 2^n (and you cannot turn your logic around), you can still avoid the expensive (and double/float) call to log2:

int bit_pos=0;
unsigned int value = ...;   // your input

while (value>1) {
  value >>= 1;
  bit_pos++;
}

bit_pos now contains the position of the highest set bit in value; if value=2^n, it will be n.

I guess there are more elegant and/or even faster ways (I would not put it past Intel or other companies to create an assembler level command for this), but I would further optimize these things only if necessary.

edited Jul 11 '16 at 15:14

answered Jul 11 '16 at 15:06

AnoE

8,048
1
21
36

Thanks! but this would onl work if I had `n`. But what I have is `2^n`. – tzippy Jul 11 '16 at 15:09
When you have only nVal `2^n` (but why? It doesn't make any sense, usually it's quite easy to keep `n` around instead, or you will scan trough most of the bits in a loop, where again keeping index is easy): you can check if your compiler has bit count function, for example gcc has `int __builtin_popcount (unsigned int x)`, so then `n = __builtin_popcount (nVal-1);` @tzippy – Ped7g Jul 11 '16 at 15:23

score 1 · Answer 2 · answered Jul 11 '16 at 15:07

1

if (mValue & (1<<n)) {
  printf("%d\n", bar[n]);
}

I'm pretty new to bit twiddling but that just might work?

answered Jul 11 '16 at 15:07

Matt

197
10

Simple way of getting the nth array element when all I have is n^2

2 Answers2