Get bit offset in C++

Question

I have an int parameter with the possible values 1,2,4,8,16,32,64.

I need to know the bit offset of the current value, i.e. for each value return 1, 2, 3, 4, 5, or 6 respectively.

What is the easiest way to achieve that?

Did you mean powers of two (6 isn’t one)? In which case the “bit offset” would be the logarithm base 2? — Konrad Rudolph, Jan 04 '12 at 15:13
The naive approach is to loop and test, but it's possible that there's a native CPU instruction that does this in one single instruction. ("get least (or most) significant bit") — Kerrek SB, Jan 04 '12 at 15:17
Sorry, the 6 should not be there, I know solve this using: log((double)val) / log(2.0); but I think this is not the right approach — kambi, Jan 04 '12 at 15:20
MSVC: _BitScanForward GCC: __builtin_ctz (easiest because you don't actually have to write any code, just call a function that already exists) — harold, Jan 05 '12 at 13:50

lezebulon · Accepted Answer · 2012-01-04T15:41:53.050

4

You have multiple answers here : http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious the easiest being, assuming you have your input value in an unsigned int v :

unsigned int r = 0; // r will be lg(v)

while (v >>= 1) // unroll for more speed...
{
  r++;
}

but it will change v in the process.

edit: in your case if you are 100% sure your input is and int and a power of 2, a look-up-table may be the simplest and fastest

edited Jan 04 '12 at 15:41

answered Jan 04 '12 at 15:20

lezebulon

7,607
11
42
73

1

What has endianess got to do with it? – Skizz Jan 04 '12 at 15:23
3

I am rather certain that your code is correct without any regard to the endianness of the hardware system on which it is running. – Sergey Kalinichenko Jan 04 '12 at 15:23
ok according to http://stackoverflow.com/questions/1041554/bitwise-operators-and-endianness endianness is not an issue, I edited my reply – lezebulon Jan 04 '12 at 15:25
Luckily it has nothing to do with endianness, otherwise we would be royally scr*wed. – Mike Nakis Jan 04 '12 at 15:26

score 1 · Answer 2 · answered Jan 04 '12 at 15:36

Here's a version that only does five iterations at most for a 32 bit value, unlike lezebulon's answer which has a worst case of 32 iterations. Adapting to 64 bit values increases the iteration count of this version to six and the other to 64 at worst.

int get_pos (unsigned v)
{
  int s=16,p=0,m=0xffff;

  while (s)
  {
    if (v>>s) p += s;
    v = (v | (v >> s)) & m;
    s >>= 1;
    m >>= s;
  }

  return p;
}

score 0 · Answer 3 · answered Jan 04 '12 at 15:57

All you need to do is loop and shift a bit each time. But there's a faster way using switch case. listing both for you.

//more code but awesomely fast
int getBitOffset1(int d) {
  switch(d) {
    case 1: return 1;
    case 2: return 2;
    case 4: return 3;
    case 8: return 4;
    case 16: return 5;
    case 32: return 6;
    /* keep adding case upto sizeof int*8 */
  }
}

//less code, the loop goes 64 times max
int getBitOffset2(int d) {
  int seed=0x01;
  int retval=0;
  do{
    if(seed<<retval == d) {
      break;
    }
    retval++;
  }while(retval<=sizeof(int)*8);
  return retval+1;
}

int main() {
    printf("%d\n", getBitOffset2(32));
    printf("%d\n", getBitOffset2(1));
    return 0;
}

Get bit offset in C++

3 Answers3