CODEWITHSUNDEEP
cbitwise-operators
md5
md5

Reputation: 23699

How to determine the number of useful bits of a number?

I'm writing a function, which determine the number of useful bits of a 16 bits integer.

int16_t
f(int16_t x)
{
    /* ... */
}

For example, the number "00000010 00100101" has 10 useful bits. I think I should use some bitwise operators, but I don't know how. I'm looking for some ways to do it.

Upvotes: 0

Views: 209

Answers (3)

Philip
Philip

Reputation: 5917

Logarithms compute the number of digits needed to represent a certain number to a certain base:

Let [x] be x, rounded to the next integer.

Then [log_b(x)] is the number of digits needed to represent x to base b.

Hence, if you want to know the number of significant bits of some x in C, then ceil(log2(x)) will tell you.


Since there is no algorithm that will tell you the number of leading zeros of a binary representation in constant time, computing the logarithm may actually be faster than naively iterating.

Upvotes: 0

Paul R
Paul R

Reputation: 212929

If you're using gcc (or a gcc-compatible compiler such as ICC) then you can use built in intrinsics, e.g.

#include <limits.h>

int f(int16_t x)
{
    return x != 0 ? sizeof(x) * CHAR_BIT - __builtin_clz(x) : 0;
}

This assumes you just want the number of bits to the right of the last leading zero bit.

For MSVC you can use _BitScanReverse with some adjustment.

Otherwise if you need this to be portable then you can implement your own general purpose clz function, see e.g. http://en.wikipedia.org/wiki/Find_first_set

Upvotes: 2

Felice Pollano
Felice Pollano

Reputation: 33242

These are called bitscan operations, and on intel architecture there are assembly instruction ( you can call directly from C ) see here. If you are using a MS compiler start from here.

Upvotes: 2

Related Questions