1

How can I get the most significative 1-bit index from an unsigned integer (uint16_t)?

Example:

uint16_t x = // 0000 0000 1111 0000 = 240
printf("ffs=%d", __builtin_ffs(allowed)); // ffs=4

There is a function (__builtin_ffs) that return the least significative 1-bit (LSB) from a unsigned integer.

I want something opposite, I want some function which returns 8 applied to above example.

Remark: I have tried building my own function but I have found some problems with datatype size, which depends by compiler.

Israel
  • 3,252
  • 4
  • 36
  • 54
  • Bit numbers should always start at zero. There are very few places where they start at 1. So your example should return 7. – Jonathon Reinhart Dec 10 '14 at 04:35
  • I agree with @JonathonReinhart, as it makes sense to have bit n represent 2^n. That said, I answered in accordance with your example. – RobP Dec 10 '14 at 04:48
  • possible duplicate of [What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?](http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i) – Jonathon Reinhart Dec 10 '14 at 04:49

2 Answers2

1

From the GCC manual at http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html:

  • Built-in Function: int __builtin_clz (unsigned int x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

So, highest set bit:

#define ONE_BASED_INDEX_OF_HIGHEST_SET_BIT(x) \
    (CHAR_BIT * sizeof 1 - __builtin_clz(x)) // 1-based index!!

beware of x == 0 or x<0 && sizeof(x)<sizeof 0 though.

Community
  • 1
  • 1
Deduplicator
  • 44,692
  • 7
  • 66
  • 118
  • What does `CHAT_BIT` mean? – Israel Dec 10 '14 at 04:28
  • 2
    @Israel [`CHAR_BIT`](http://stackoverflow.com/a/3200969/119527) is the number of bits in a `char` (byte) - nowdays, normally 8. – Jonathon Reinhart Dec 10 '14 at 04:29
  • Since `__builtin_clz()` takes an unsigned int argument, I think it should be `CHAR_BIT * sizeof int - __builtin_clz(x)`, since `x` will be promoted to int. Also note the lack of "-1" because the OP numbers bits starting from 1 and wants his example to return 8. – JS1 Dec 10 '14 at 04:34
0

if I am reading this right (am I? I'm a little rusty on this stuff) you can do this as follows:

int msb = 0;
while(x) { // while there are still bits
    x >>= 1; // right-shift the argument
    msb++; // each time we right shift the argument, increment msb
}
Jonathon Reinhart
  • 132,704
  • 33
  • 254
  • 328
RobP
  • 9,144
  • 3
  • 20
  • 33
  • `x>>1;` has no effect. I edited your answer to do what you intended. However, I believe this still produces an answer that is off by one. – Jonathon Reinhart Dec 10 '14 at 04:39
  • @JonathonReinhart thank you for the correction. As for off by one, are you sure? 0 returns 0, 1 returns 1, 2 (0x10) or 3(0x11) return 2, etc... – RobP Dec 10 '14 at 04:41
  • `Test value: 0x0000F00D __builtin_clz: 16 Deduplicator: 15 RobP: 16` – Jonathon Reinhart Dec 10 '14 at 04:42
  • comment on Deduplicator's answer: Also note the lack of "-1" because the OP numbers bits starting from 1 and wants his example to return 8. – RobP Dec 10 '14 at 04:42
  • Ah, I suppose you are technically correct. Removed my downvote, as this is much closer now. – Jonathon Reinhart Dec 10 '14 at 04:44