P: n/a

Hi,
does anyone know of an efficient way to find the number of
digits (i.e. the most significant position that is 1) of a
binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2
 shifting until 0: for(j=0; number>>=1; j++); digits = j;
 binary search shifting
Any better ideas?
Thanks and regards,
Christof  
Share this Question
P: n/a

CHRISTOF WARLICH wrote: Hi,
does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2  shifting until 0: for(j=0; number>>=1; j++); digits = j;  binary search shifting
Any better ideas?
Thanks and regards,
Christof
if your binary number is small enough, a table lookup may suffice...
David  
P: n/a

* CHRISTOF WARLICH: does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2
Very inefficient unless you have a fast integer log function
(which in that case is exactly what you're looking for).
 shifting until 0: for(j=0; number>>=1; j++); digits = j;
Use ++j, and stylewise add an empty loop body, {}.
 binary search shifting
Any better ideas?
You could always use a table, dividing the number up in chunks
in a binary search until suitable for the table size.
But that is inefficient in terms of memory usage.
You don't specify what you mean by "efficient".

A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Topposting.
Q: What is the most annoying thing on usenet and in email?  
P: n/a

CHRISTOF WARLICH wrote: Hi,
does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2  shifting until 0: for(j=0; number>>=1; j++); digits = j;  binary search shifting
Any better ideas?
Thanks and regards,
Christof
There are a number of implementations of "ffs" or "find first set" and
on most linux boxen it's available as int ffs(int) in string.h.
However, this is a cute trick. Converting an integer to floating point
will give you the number you're looking for in the exponent.
std::frexp() will extract the exponent ...
#include <cmath>
int ffs_fp( int value )
{
if ( value == 0 )
{
return 1; // no answer
}
int exponent;
double correct_mantissa = std::frexp( value, &exponent );
return exponent 1;
}
#include <iostream>
void testit( int value )
{
std::cout << "ffs_fp( " << value << " ) = " << ffs_fp( value ) << "\n";
}
int main()
{
testit( 1 << 2 );
testit( 1 << 0 );
testit( 1 << 17 );
testit( 1 + ( 1 << 17 ) );
}  
P: n/a

Hi,
Binary search initially and then table lookup. For example if you can spare
64kb for a lookup table and your numbers are up to 32bit (untested code):
char lookup[0x10000];
int digits(unsigned int n)
{
if (n < 0x10000)
return lookup[n];
else
return 16 + lookup[n >> 16];
}
Regards,
Marcin
Uzytkownik "CHRISTOF WARLICH" <cw******@lucent.com> napisal w wiadomosci
news:41***************@lucent.com... Hi,
does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2  shifting until 0: for(j=0; number>>=1; j++); digits = j;  binary search shifting
Any better ideas?
Thanks and regards,
Christof  
P: n/a

CHRISTOF WARLICH <cw******@lucent.com> wrote in message news:<41***************@lucent.com>... Hi,
does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2  shifting until 0: for(j=0; number>>=1; j++); digits = j;  binary search shifting
Any better ideas?
Assembly an option? IIRC there are some CPU archs which have exactly
this instruction, and it is very hard to outoptimize microcode.
If not, I'd probably break the number up in 8bits chunks and use
a 256 entry lookup. For 32bits numbers, that's 2 or 3 comparisons
(I don't know which approach is faster, 3 checks against 0 of 2
checks against constants)
HTH,
Michiel Salters  
P: n/a

CHRISTOF WARLICH wrote: Hi,
does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2  shifting until 0: for(j=0; number>>=1; j++); digits = j;  binary search shifting
Any better ideas?
You might like to look at this site that gives some techniques for this
sort of problem: http://www.hackersdelight.org/HDcode.htm
Brian Gladman  
P: n/a

> > does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2
Very inefficient unless you have a fast integer log function (which in that case is exactly what you're looking for).
If number does not fit into an int, then it might be a good idea.  shifting until 0: for(j=0; number>>=1; j++); digits = j;
Use ++j, and stylewise add an empty loop body, {}.
Why ++j ? In all other cases, the recipient of the value is left of the
operator: f.ex j+=2, object.inc(), so why not j++ that would be more conform
to the C++ style.
Niels Dybdahl  
P: n/a

"David Lindauer" <ca*****@bluegrass.net> wrote in message if your binary number is small enough, a table lookup may suffice...
If the binary number is big, then you can use the table lookup many times.
For example, if your table handles integers whose sizeof equals 1 (eg.
char), then to handle an integer whose sizeof is 4 (eg. int on many
platforms), then use the table up to 4 times.  
P: n/a

"Niels Dybdahl" <nd*@fjern.detteeskographics.com> skrev i en meddelelse
news:41*********************@news.dk.uu.net... > does anyone know of an efficient way to find the number of > digits (i.e. the most significant position that is 1) of a > binary number? What I found so far is: > >  digits = (int) log2(number), where log 2 means log for base 2
Very inefficient unless you have a fast integer log function (which in that case is exactly what you're looking for).
If number does not fit into an int, then it might be a good idea.
>  shifting until 0: for(j=0; number>>=1; j++); digits = j;
Use ++j, and stylewise add an empty loop body, {}.
Why ++j ? In all other cases, the recipient of the value is left of the operator: f.ex j+=2, object.inc(), so why not j++ that would be more conform to the C++ style.
Niels Dybdahl
Always prefer ++x to x++  this is an efficiency issue.
/Peter  
P: n/a

Thanks to all!
Regards,
Christof
CHRISTOF WARLICH wrote: Hi,
does anyone know of an efficient way to find the number of digits (i.e. the most significant position that is 1) of a binary number? What I found so far is:
 digits = (int) log2(number), where log 2 means log for base 2  shifting until 0: for(j=0; number>>=1; j++); digits = j;  binary search shifting
Any better ideas?
Thanks and regards,
Christof  
P: n/a

"Peter Koch Larsen" <pk*****@mailme.dk> wrote in message news:ZrDpd.70127 Always prefer ++x to x++  this is an efficiency issue.
This doesn't matter for fundamental types, which is the subject of this
thread.  
P: n/a

* Siemel Naran: "Peter Koch Larsen" <pk*****@mailme.dk> wrote in message news:ZrDpd.70127
Always prefer ++x to x++  this is an efficiency issue.
This doesn't matter for fundamental types, which is the subject of this thread.
<rant>
The reason I advocate the ++x style is that I feel that in programming
one should strive to be _exact_ and specify only what one wants
accomplished  not instantiate a webbrowser component in order to
display some simple text in the user interface (say), because that's
easiest using the IDE's drag'n'drop interface, which is the end result
of accustomizing oneself to being imprecise and just adding things until
the hodgepodge seems to work.
</rant>
;)

A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Topposting.
Q: What is the most annoying thing on usenet and in email?  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> skrev i en meddelelse
news:Ey*******************@bgtnsc05news.ops.worldnet.att.net... "Peter Koch Larsen" <pk*****@mailme.dk> wrote in message news:ZrDpd.70127
Always prefer ++x to x++  this is an efficiency issue.
This doesn't matter for fundamental types, which is the subject of this thread.
So what? It is simply a matter of style  use the form that is efficient all
the time.
/Peter   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 6339
 replies: 13
 date asked: Jul 22 '05
