Hi all,
I need a simple algorithm to tell me how many bits any particular number needs.
For example, if I send the function the value "61" (decimal), I want it to return "6" (because you need 6 bits to handle up to 63).
Likewise, if I send the function "1000" decimal, I want it to return "10" (decimal).
I can do this any number of ways, but I'm assuming that there is a small, standard, elegant way to do it and I'm wondering if any of you know it.
Thanks!
-- Roger
Simplest way is to place the number into a single variable large enough to store the biggest number you'll be dealing with, then left-shift (and count) until the left-most bit (MSB) is not zero, then subtract that count from the size of the variable.
Something like:
int bits(unsigned int val) { // Should work with any size integer.
unsigned int maxbits = sizeof(val) * 8;
unsigned int mask = 1 << maxbits-1; // Make sure this is the same size as val
unsigned int count = 0;
while (((val & mask) == 0) && (count < maxbits)) {
val <<= 1;
count++;
}
return maxbits - count;
}
maybe.
What majenko said, except that there is a simplification (assuming that all of the numbers are positive):
Right shift and count the number of shifts until the result is zero.
If the number could be negative, I don't think that my method or majenko's method works. In that case, I think that I would want to treat (sign bit == 1, all other bits == 0) as a special case, and otherwise take the absolute value. Follow this up with my method or the one from majenko.
Alternative that doesn't modify the value (if that matters...):
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);
This code will never return "requires 0 bits" due to the size + 1 and the structure of the loop. If you want that to be a valid option, you'll need to tweak the loop or special-case it with something like:
// Intentionally overflow this unsigned integer value
if (testval == 0) size = (0 - 1);
Serial.println("Value %lu requires %u bits\n", testval, size + 1);
Thank you all for the replies so far. I ended up figuring this out myself in the course of trying to to the rest of what I'm trying to do... which is reversing the bit order of any arbitrary number (up to 64 bits long).
Here's what I have so far, but the voices in my head are telling me what I have is clumsy and can be done easier, but I'm not seeing it. Any input here would be appreciated!
uint64_t bitreverse (uint64_t value)
{
uint8_t bits = 0;
uint8_t x;
uint64_t tmp = 1;
while (value / tmp) {
bits++;
tmp <<= 1;
}
tmp = 0;
x = bits;
while (bits--) {
// put the bits into the high end...
tmp |= (value & _BV(bits)) ? _BV(x) : 0;
// ...and shift them down to the low end
tmp >>= 1;
}
return tmp; // return value bit-reversed
}
I would be wary of using this, since "an arbitrary number of bits" may not be the native word length of the value you want to reverse. (That is, are you sure the value's real MSB will always be set to 1?) What's the application context of this function?
It's easy to reverse a 64-bit number, or a modulo-8-bit number, or an arbitrary-length number ... but it's harder to guess the appropriate word length without knowing what the value's max can (or will or should) be.
Krupski:
I need a simple algorithm to tell me how many bits any particular number needs.For example, if I send the function the value "61" (decimal), I want it to return "6" (because you need 6 bits to handle up to 63).
Likewise, if I send the function "1000" decimal, I want it to return "10" (decimal).
Others seem to think you want to count the bits in any given number. I think you want fo find out how many bits it requires to store a number.
I am limiting my method to unsigned numbers, long or shorter.
void setup() {
Serial.begin(115200);
for (int i = 0; i < 1024; i++) {
Serial.print ( i );
Serial.print(" ");
Serial.println(numBits(i));
}
for (unsigned long i = 0xfffffff0; i <= 0xfffffffe; i++) {
Serial.print ( i );
Serial.print(" ");
Serial.println(numBits(i));
}
}
void loop() {
// put your main code here, to run repeatedly:
}
byte numBits(unsigned long testNum) {
byte i;
unsigned long val = 1;
for( i = 1; i < 32 ; (i++)) {
val = val << 1;
if (val > testNum) {
return i;
}
}
return i;
}
lar3ry:
Others seem to think you want to count the bits in any given number. I think you want fo find out how many bits it requires to store a number.
How do those two things differ exactly?
My concern is, with an input of "1", what is the correct output?
1?
128?
32768?
2.147M?
9.22e18?
SirNickity:
lar3ry:
Others seem to think you want to count the bits in any given number. I think you want fo find out how many bits it requires to store a number.How do those two things differ exactly?
My concern is, with an input of "1", what is the correct output?
1?
128?
32768?
2.147M?
9.22e18?
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.
I agree, its a minimum storage width, not a count of asserted bits.
Here is my take, might not be the quickest ( untested ), however its straightforward.
const unsigned char MinimumBits( const unsigned long long &ull ){
switch( ull ){
case 0x00 ... 0xFF: return 8;
case 0x100 ... 0xFFFFU: return 16;
case 0x10000UL ... 0xFFFFFFFFUL: return 32;
case 0x100000000ULL ... 0xFFFFFFFFFFFFFFFFULL: return 64;
}
}
void setup(){
Serial.begin( 9600 );
Serial.println( MinimumBits( 10 ) );
Serial.println( MinimumBits( 12345 ) );
Serial.println( MinimumBits( 123456789 ) );
Serial.println( MinimumBits( 9.0E38 ) );
}
void loop() {}
SirNickity:
lar3ry:
Others seem to think you want to count the bits in any given number. I think you want fo find out how many bits it requires to store a number.How do those two things differ exactly?
My concern is, with an input of "1", what is the correct output?
1?
128?
32768?
2.147M?
9.22e18?
My sense of the problem seems to coincide with this.
To my way of thinking the number of bits in a number is irrelevant apart from as a code for the value of the number. In Arduino programming what matters is the type of the variable in which the number is stored. That is what defines the number of bits. Consider, for example, the different representation of -7 in an INT and in a LONG.
If there is some need to reverse a number the logic should be designed at the number level, not at the bit level.
...R
int bitCount (unsigned long n)
{
n = (n & 0x55555555) + ((n >> 1) & 0x55555555) ;
n = (n & 0x33333333) + ((n >> 2) & 0x33333333) ;
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f) ;
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff) ;
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff) ;
return n ;
}
It's quick on a 32 bit (or greater) processor, but I haven't tried it on an 8 bitter.
To find the most significant bit set, use "__builtin_clz" (Count Leading Zeroes)
Returns the number of bit positions occupied in a value:
uint64_t bitcount (uint64_t val)
{
for (int i = 64; (i >= 0) && (val > 0); i--) {
if ((val & 0x8000000000000000) == 0x8000000000000000) {
return i;
}
val = val << 1;
}
}
@AWOL & @dlloyd, both those functions are nice, however they do not satisfy the requirements.
"I need a simple algorithm to tell me how many bits any particular number needs."
bits needed, not bits set.
My simple range select, and lar3ry's do.
It returns bits needed, not bits set. 4 dec returns 3, 7 dec returns 3, 8 dec returns 4, etc.
dlloyd:
It returns bits needed, not bits set. 4 dec returns 3, 7 dec returns 3, 8 dec returns 4, etc.
Ahh, yes sorry. Misleading name and description.
""__builtin_clz" is the one to use - why reinvent the wheel?
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.
// takes time linear with # bits
uint8_t bitsNeeded(long x)
{
uint8_t n = 0;
do
{
x >>= 1;
n++;
}
while(x > 0);
return n;
}
void setup()
{
Serial.begin(115200);
Serial.println("Start ");
for (int i=0; i< 258; i++)
{
Serial.print(i,DEC);
Serial.print("\t");
Serial.println(bitsNeeded(i), DEC);
}
}
void loop()
{
}
AWOL:
""__builtin_clz" is the one to use - why reinvent the wheel?
because
#define BITS(X) ( 64 - __builtin_clzll((long long)X))
gives a wrong value for 0 ?
robtillaart:
AWOL:
""__builtin_clz" is the one to use - why reinvent the wheel?because
#define BITS(X) ( 64 - __builtin_clzll((long long)X))gives a wrong value for 0 ?
It does?