find number of digits

C

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
 
D

David Lindauer

CHRISTOF said:
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
 
A

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

Gianni Mariani

CHRISTOF said:
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 ) );

}
 
M

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
 
M

Michiel Salters

CHRISTOF WARLICH said:
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
 
B

BRG

CHRISTOF said:
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
 
N

Niels Dybdahl

does anyone know of an efficient way to find the number of
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.
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
 
S

Siemel Naran

David Lindauer said:
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

Peter Koch Larsen

Niels Dybdahl said:
If number does not fit into an int, then it might be a good idea.


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
 
S

Siemel Naran

Peter Koch Larsen said:
Always prefer ++x to x++ - this is an efficiency issue.

This doesn't matter for fundamental types, which is the subject of this
thread.
 
A

Alf P. Steinbach

* Siemel Naran:
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>

;-)
 
P

Peter Koch Larsen

Siemel Naran said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top