Determine how many bits in a value

Projects Programming
28

Didn't know about __builtin_clz... learn something new every day. 8)

lar3ry:

SirNickity:
How do those two things differ exactly?

They differ in the most fundamental way.

If an unsigned byte, int, or long holds a value of 128, it will contain a single bit that is set to 1.
That same unsigned byte, int, or long requires 8 bits to hold the value of 128.

The OP said

I need a simple algorithm to tell me how many bits any particular number needs.

So, 128 requires 8 bits to hold the value. The OP did not ask for a method to tell him how many bits are set to 1.
Clearly, 128 requires 8 bits to represent that number. One of them is a 1, and seven of them are 0s.

pYro_65:
bits needed, not bits set.
My simple range select, and lar3ry's do.

Who was talking about counting set bits? :~ That's not what my example code does....

uint32_t testval = 1337;
uint8_t size = 32;  // Set to maximum width of container variable

while (size) {
    size--;
    if (testval & (1 << size)) break;
}

Serial.println("Value %lu requires %u bits\n", testval, size + 1);

linux ~/dev/c $ ./test 42
Value 42 requires 6 bits
linux ~/dev/c $ ./test 1337
Value 1337 requires 11 bits
linux ~/dev/c $ ./test 4000000000
Value 4000000000 requires 32 bits
linux ~/dev/c $ ./test 3         
Value 3 requires 2 bits
linux ~/dev/c $

robtillaart:
The number of bits needed is INT(2log(x) +1) assuming it has no sign bit.

n = int(log(x)/log(2) + 1);

as this takes an expensive float operation one can use a simple loop.

Well.... +1 for excellent technical observation. But, -1 for an expensive implementation. :wink: heheh

Krupski:
Thank you all and especially you AWOL because your code helped me on the path to the solution I needed!

Your code reverses all the bits (OK so far) but it doesn't return the result I need. For example:

Input: 0b111001
Desired output: 0b100111
Actual output: 0b10011100000000000000000000000000

The solution is to slide off the bits I don't want. The final result (which does what I need for any number) is the following:

So, is 0b100111 the result you want because the result is a 6-bit number, or is it what you want because the input requires 6 bits to represent? I still don't quite understand the application for a backwards, variable-length binary representation of an arbitrary number. I guess I don't need to understand, but I am awfully curious why this is something anyone needs to do... :~