By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,786 Members | 1,131 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,786 IT Pros & Developers. It's quick & easy.

find number of digits

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
Jul 22 '05 #1
Share this Question
Share on Google+
13 Replies


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
Jul 22 '05 #2

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: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 22 '05 #3

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 ) );

}
Jul 22 '05 #4

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



Jul 22 '05 #5

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 out-optimize microcode.

If not, I'd probably break the number up in 8-bits chunks and use
a 256 entry lookup. For 32-bits 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
Jul 22 '05 #6

P: n/a
BRG
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
Jul 22 '05 #7

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
Jul 22 '05 #8

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.
Jul 22 '05 #9

P: n/a

"Niels Dybdahl" <nd*@fjern.detteesko-graphics.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
Jul 22 '05 #10

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

Jul 22 '05 #11

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.

Jul 22 '05 #12

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 web-browser 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: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 22 '05 #13

P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> skrev i en meddelelse
news:Ey*******************@bgtnsc05-news.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
Jul 22 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.