find number of digits

[CHRISTOF WARLICH]

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

[David Lindauer]

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

[Alf P. Steinbach]

* 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?

[Gianni Mariani]

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

}

[Marcin Kalicinski]

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

[Michiel Salters]

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

[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

[Niels Dybdahl]

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

[Siemel Naran]

"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.

[Peter Koch Larsen]

"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

[CHRISTOF WARLICH]

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

[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.

[Alf P. Steinbach]

* 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?

[Peter Koch Larsen]

"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