434,786 Members | 1,131 Online
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
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 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 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" 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 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 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" 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" 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" 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" 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. 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. ;-) -- 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" skrev i en meddelelse news:Ey*******************@bgtnsc05-news.ops.worldnet.att.net... "Peter Koch Larsen" 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.