How to get the position of the first set bit of a number

Question

for example, my definition looks like the following:

#define AA              0x0000000000000001LL
#define BB              0x0000000000000002LL
#define CC              0x0000000000000004LL
#define DD              0x0000000000000008LL
#define EE              0x0000000000000010LL
#define FF              0x0000000000000020LL
#define GG              0x0000000000000040LL
#define HH              0x0000000000000080LL

I would like to get the position of the first set bit (counting backwards from the least significant bit) from the maximum definition.

h = getAmountFromBitwise(HH);
output of h is 8;
b = getAmountFromBitwise(BB);
output b is 2;

Is there any better way to implement getAmountFromBitwise()?

int getAmountFromBitwise(long long input) {
  2^x = input;
  y=x+1;
  return y;
}

The definations are defined in sequence, 0x01, 0x02, 0x04, 0x8, 0x10, ...., every next value are multiple by 2 from previous one. — srjohnhuang, Jan 21 '15 at 08:40
Are you saying that you want a function to identify the most-significant bit set in its argument? — M.M, Jan 21 '15 at 08:43
@MattMcNabb: Seems like the index of **L**SB, index starting at 1. — Zeta, Jan 21 '15 at 08:48
your function doesn't even compile because `2^x = input;` is invalid and x and y weren't declared before. And this is not the "amount" but the bit position — phuclv, Jan 21 '15 at 08:51
possible duplicate: http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set — phuclv, Jan 21 '15 at 08:54
@LưuVĩnhPhúc, it is just my pseudo code. i want to know how do i get the y. — srjohnhuang, Jan 21 '15 at 08:54
best way: `__builtin_ctz` in gcc and `_BitScanReverse` in MSVC http://en.wikipedia.org/wiki/Find_first_set — phuclv, Jan 21 '15 at 08:56
@LưuVĩnhPhúc Wouldn't that be [`_BitScanForward`](https://msdn.microsoft.com/en-us/library/vstudio/wfd9z0bb%28v=vs.100%29.aspx)? — legends2k, Jan 21 '15 at 09:40

score 3 · Accepted Answer · answered Jan 21 '15 at 09:32

3

I would use this as your getAmountFromBitwise().

int highest_bit_set(long long n) {
  int result = 1;
  while(n >>= 1) /* keep shifting right until n == 0 */
    result++;
  return result;
}

Note that this requires that n != 0 for a correct result.

answered Jan 21 '15 at 09:32

Hans Lub

5,513
1
23
43

How to get the position of the first set bit of a number

1 Answers1