Re: from number to power of two
According to Brian F. Feldman: -O lets you do explicit inlining, and -O2 enables -finline-functions. You meant -O3 of course. -O3Optimize yet more. This turns on everything -O2 does, along with also turning on -finline-func- tions. -- Ollivier ROBERT -=- FreeBSD: The Power to Serve! -=- robe...@keltia.freenix.fr FreeBSD keltia.freenix.fr 4.0-CURRENT #73: Sat Jul 31 15:36:05 CEST 1999 To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Mark Murray scribbled this message on Aug 22: Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. Shift a bit until it becomes greater than (or less than) the number in question. ummm, didn't you read his post?? he wanted a O(1) routine, NOT a O(n) routine... -- John-Mark Gurney Voice: +1 541 684 8449 Cu Networking P.O. Box 5693, 97405 "The soul contains in itself the event that shall presently befall it. The event is only the actualizing of its thought." -- Ralph Waldo Emerson To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
John-Mark Gurney wrote: Shift a bit until it becomes greater than (or less than) the number in question. ummm, didn't you read his post?? he wanted a O(1) routine, NOT a O(n) routine... That technique is O(ln(n)), where n is the number in question. Frankly, for numbers up to 32, a table will wield the best results, and might actually be smaller than some of the suggestions given so far. -- Daniel C. Sobral(8-DCS) [EMAIL PROTECTED] [EMAIL PROTECTED] - Come on. - Where are we going? - To get what you came for. - What's that? - Me. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
According to Brian F. Feldman: -O lets you do explicit inlining, and -O2 enables -finline-functions. You meant -O3 of course. -O3Optimize yet more. This turns on everything -O2 does, along with also turning on -finline-func- tions. -- Ollivier ROBERT -=- FreeBSD: The Power to Serve! -=- [EMAIL PROTECTED] FreeBSD keltia.freenix.fr 4.0-CURRENT #73: Sat Jul 31 15:36:05 CEST 1999 To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. Shift a bit until it becomes greater than (or less than) the number in question. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Mark Murray scribbled this message on Aug 22: Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. Shift a bit until it becomes greater than (or less than) the number in question. ummm, didn't you read his post?? he wanted a O(1) routine, NOT a O(n) routine... -- John-Mark Gurney Voice: +1 541 684 8449 Cu Networking P.O. Box 5693, 97405 The soul contains in itself the event that shall presently befall it. The event is only the actualizing of its thought. -- Ralph Waldo Emerson To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
It seems that all the solutions are too generic and slow. As I only have to check the numbers 0-32 (actually 1-32), a block of if statements is almost as fast as a table look up in 33 elements. Cheers, Nick On Sun, 22 Aug 1999, Mark Murray wrote: Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. Shift a bit until it becomes greater than (or less than) the number in question. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org -- e-Mail: hi...@skylink.it To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
John-Mark Gurney wrote: Shift a bit until it becomes greater than (or less than) the number in question. ummm, didn't you read his post?? he wanted a O(1) routine, NOT a O(n) routine... That technique is O(ln(n)), where n is the number in question. Frankly, for numbers up to 32, a table will wield the best results, and might actually be smaller than some of the suggestions given so far. -- Daniel C. Sobral(8-DCS) d...@newsguy.com d...@freebsd.org - Come on. - Where are we going? - To get what you came for. - What's that? - Me. To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
It seems that all the solutions are too generic and slow. As I only have to check the numbers 0-32 (actually 1-32), a block of if statements is almost as fast as a table look up in 33 elements. I doubt it - use the table for a small fixed size set then use Warner's (n) ? (1 (ffs(n) - 1)) : 0. The possible inline ffs is in machine/cpufunc.h ffs() is fundamental to scheduling queues and cryptography and should have attention paid to it. As Warner said, it could be a single instruction on some architectures. Peter -- Peter Dufault (dufa...@hda.com) Realtime development, Machine control, HD Associates, Inc. Safety critical systems, Agency approval To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Daniel C. Sobral d...@newsguy.com wrote That technique is O(ln(n)), where n is the number in question. Frankly, for numbers up to 32, a table will wield the best results, and might actually be smaller than some of the suggestions given so far. Counting n as bit, it is O(n) :p Unrolling the loop, if(n=2^0) 2^0 else if(n=2^1) 2^1 else if(n=2^2) 2^2 else if(n=2^3) 2^3 : : else if(n=2^31) 2^31 is suitable for this problem? --- //mit To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Unfortunately the kernel is compiled with -O which does not include inlining (dunno about explicit inlining, but don't think so). Nick On Sun, 22 Aug 1999, Peter Dufault wrote: It seems that all the solutions are too generic and slow. As I only have to check the numbers 0-32 (actually 1-32), a block of if statements is almost as fast as a table look up in 33 elements. I doubt it - use the table for a small fixed size set then use Warner's (n) ? (1 (ffs(n) - 1)) : 0. The possible inline ffs is in machine/cpufunc.h ffs() is fundamental to scheduling queues and cryptography and should have attention paid to it. As Warner said, it could be a single instruction on some architectures. Peter -- Peter Dufault (dufa...@hda.com) Realtime development, Machine control, HD Associates, Inc. Safety critical systems, Agency approval -- e-Mail: hi...@skylink.it To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
--- Kazufumi-MIT-Mitani m...@mit-s.otaru-uc.ac.jp skrev: Daniel C. Sobral d...@newsguy.com wrote That technique is O(ln(n)), where n is the number in question. Frankly, for numbers up to 32, a table will wield the best results, and might actually be smaller than some of the suggestions given so far. Counting n as bit, it is O(n) :p No it isn't. You're only looping a maximum of 32 times, not 2^32 times. Unrolling the loop, if(n=2^0) 2^0 else if(n=2^1) 2^1 else if(n=2^2) 2^2 else if(n=2^3) 2^3 : : else if(n=2^31) 2^31 is suitable for this problem? IMHO, the best solution so far, if a lookup table isn't suitable, is the binary search version that someone posted. Regards, Tommy === Tommy Hallgren Briljantg. 31, SE-421 49, Göteborg Tel.: 0709 - 312 404 (GSM) Tel.: 031 - 47 65 28 (Home) __ Do You Yahoo!? Bid and sell for free at http://auctions.yahoo.com To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Peter Dufault wrote:
It seems that all the solutions are too generic and slow. As I only have
to check the numbers 0-32 (actually 1-32), a block of if statements is
almost as fast as a table look up in 33 elements.
I doubt it - use the table for a small fixed size set then
use Warner's (n) ? (1 (ffs(n) - 1)) : 0.
The possible inline ffs is in machine/cpufunc.h
ffs() is fundamental to scheduling queues and cryptography and
should have attention paid to it. As Warner said, it could be
a single instruction on some architectures.
ffs() works from the wrong direction though. He needs the MSB, not the LSB.
There is a fls() inline in machine/cpufunc.h though, at least for the x86
family which I think will return the bit number (range: 32 - 1) of the MSB.
So, to get the rounded down (and up) power-of-two value you'd do:
#include sys/types.h
#include machine/cpufunc.h
#include stdio.h
main()
{
int i, down, up;
for (i = 0; i 65; i++) {
down = i ? (1 (fls(i) - 1)) : 0;
up = 1 fls(i);
printf(%d %d %d\n, i, down, up);
}
}
I'm not sure what you want at zero, but the result is:
0 0 1
1 1 2
2 2 4
3 2 4
4 4 8
5 4 8
6 4 8
7 4 8
8 8 16
9 8 16
10 8 16
11 8 16
12 8 16
13 8 16
14 8 16
15 8 16
16 16 32
17 16 32
The is normally implemented as a barrel shift on most modern CPU's.
The other key trick is (x) -(x). That returns the LSB in position, not
the bit number.
ie: 12 -12 =
1100
0100 (twos complement, in byte form)
= 0100 = 4 = the value of the LSB.
Cheers,
-Peter
--
Peter Wemm - pe...@freebsd.org; pe...@yahoo-inc.com; pe...@netplex.com.au
To Unsubscribe: send mail to majord...@freebsd.org
with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
On Sun, 22 Aug 1999, Nick Hibma wrote: Unfortunately the kernel is compiled with -O which does not include inlining (dunno about explicit inlining, but don't think so). Nick -O lets you do explicit inlining, and -O2 enables -finline-functions. Anyway, I think the simple solution to the problem for this case is a switch, since GCC creates optimizations nicely with those :) -- Brian Fundakowski Feldman / Any sufficiently advanced bug is\ gr...@freebsd.org | indistinguishable from a feature. | FreeBSD: The Power to Serve!\-- Rich Kulawiec / To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
The best I can come up with is this:
/* kk+1 k
* given n, return 2 such that 2 n = 2
*/
inline unsigned long
n2power2(unsigned long n)
{
/* `smear' the highest set bit to the right */
n |= n1; n |= n2; n |= n4; n |= n8; n |= n16;
/* now n is of the form 0..01..1 */
return n ~(n1);
}
Note that n bit shift is also O(n) on many machines but
usually a machine instruction implements it so this may still
be faster than 5 or 6 compares and branches that you would
need if a binary search was used. But
n ? 1 (fls(n)-1) : 0
where fls is inlined may still beat it!
-- bakul
To Unsubscribe: send mail to majord...@freebsd.org
with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
G'day Nick, Nick Hibma [EMAIL PROTECTED] wrote: Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. a bitwise shift left (to higher) or right (to lower) before or after masking out all but the most significant bit in the number. You just need to know how many bits to mask based on where the most significant bit is ;] I was tempted to throw something together but its late, and the idea should be enough to go on ... Cheers Leigh -- | "By the time they had diminished | Leigh Hart, [EMAIL PROTECTED] | | from 50 to 8, the other dwarves | CCNA - http://www.cisco.com/ | | began to suspect 'Hungry' ..." | GPO Box 487 Adelaide SA 5001 | | -- Gary Larson, "The Far Side" | http://www.dotat.com/hart/ | To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. The only solution I have so far is a table. That is a possibility as the the highest number will be 32 I think. The kernel uses a 'ffs()' function for that but i seem to remember that some processors have this one as a machine instruction. ffs() is declared in /sys/sys/libkern.h and implemented in /sys/libkern/ffs.c but maybe there is an assembly version somewherewhich i can't find. cheers luigi To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3 - 2
4,5,6,7 - 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
Nick,
Probably the best solution I can think of is a binary search on the
number. I'd estimate it as better than a table, as you save on memory
references (tables sound cool, but, from experience, they cause enough
extra data cache misses to kill any advantage, even in
a highly-optimized inner loop.
For 8-bit integets, a quick solution is:
int
round_up(int x)
{
if (x 0xf0) {
if (x 0xc0)
return (x 0x80) ? 0x80 : 0x40;
else {
return (x 0x20) ? 0x20 : 0x10;
}
}
else {
if (x 0xc)
return (x 0x8) ? 0x8 : 0x4;
else {
return (x 0x2) ? 0x2 : 0x1;
}
}
}
It's actually faster than the BSF/BSR operations on Pentium (and the
ffs() libc function), as Pentium does a sequential search of the bit
string and therefore is O(n) (eek!)
The innermost comparison could probably be avoided if it wasn't 00:37
or if I didn't have to get up early in the morning. You could also
combine that with a smaller lookup table to get the best of both
worlds.
Patryk.
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
At Sat, 21 Aug 1999 12:54:32 +0200, Nick Hibma wrote:
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3- 2
4,5,6,7- 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
This small prog works at least on x86
=
#include sys/types.h
#include machine/cpufunc.h
int
main(int argc, char **argv){
int i, j, k;
sscanf(argv[1], "%d", i);
j = 1(fls(i)-1);
k = 1(fls(i-1));
printf("%d %d %d\n", j, i, k);
return 0;
}
=
/Johan K
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
In message [EMAIL PROTECTED] Nick Hibma writes: : Does anyone know an inexpensive algorithm (O(1)) to go from an number to : the next (lower or higher) power of two. 1 ffs(x) Warner To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: from number to power of two
Nick Hibma scribbled this message on Aug 21:
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3 - 2
4,5,6,7 - 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
hmmm how about:
int
fls(int n)
{
/* courtesy of fortune, of course this is O(lgn) */
/* swap the bits around */
n = ((n 1) 0x) | ((n 1) 0x);
n = ((n 2) 0x) | ((n 2) 0x);
n = ((n 4) 0x0f0f0f0f) | ((n 4) 0xf0f0f0f0);
n = ((n 8) 0x00ff00ff) | ((n 8) 0xff00ff00);
n = ((n 16) 0x) | ((n 16) 0x);
/* mask all but the lowest bit off */
n = n -n;
/* swap them back to where they were originally */
n = ((n 1) 0x) | ((n 1) 0x);
n = ((n 2) 0x) | ((n 2) 0x);
n = ((n 4) 0x0f0f0f0f) | ((n 4) 0xf0f0f0f0);
n = ((n 8) 0x00ff00ff) | ((n 8) 0xff00ff00);
n = ((n 16) 0x) | ((n 16) 0x);
return n;
}
now this is O(lgn) (where n is number of bits in an int), but I'm not
sure how this will perform wrt the other posting.. it probably won't be
that fast because of all the arithmetic that happens, and a binary search
of the number would probably be faster (which I have implemented a few
times)...
--
John-Mark Gurney Voice: +1 541 684 8449
Cu Networking P.O. Box 5693, 97405
"The soul contains in itself the event that shall presently befall it.
The event is only the actualizing of its thought." -- Ralph Waldo Emerson
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-hackers" in the body of the message
from number to power of two
Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. The only solution I have so far is a table. That is a possibility as the the highest number will be 32 I think. Nick -- e-Mail: hi...@skylink.it To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
G'day Nick, Nick Hibma n_hi...@skylink.it wrote: Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. a bitwise shift left (to higher) or right (to lower) before or after masking out all but the most significant bit in the number. You just need to know how many bits to mask based on where the most significant bit is ;] I was tempted to throw something together but its late, and the idea should be enough to go on ... Cheers Leigh -- | By the time they had diminished | Leigh Hart, h...@dotat.com | | from 50 to 8, the other dwarves | CCNA - http://www.cisco.com/ | | began to suspect 'Hungry' ... | GPO Box 487 Adelaide SA 5001 | | -- Gary Larson, The Far Side | http://www.dotat.com/hart/ | To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Does anyone know an inexpensive algorithm (O(1)) to go from an number to the next (lower or higher) power of two. 1 - 1 2,3 - 2 4,5,6,7 - 4 8,9,10,11,12,13,14,15 - 8 etc. So %1101 should become either %1 or %1000. The only solution I have so far is a table. That is a possibility as the the highest number will be 32 I think. The kernel uses a 'ffs()' function for that but i seem to remember that some processors have this one as a machine instruction. ffs() is declared in /sys/sys/libkern.h and implemented in /sys/libkern/ffs.c but maybe there is an assembly version somewherewhich i can't find. cheers luigi To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3 - 2
4,5,6,7 - 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
Nick,
Probably the best solution I can think of is a binary search on the
number. I'd estimate it as better than a table, as you save on memory
references (tables sound cool, but, from experience, they cause enough
extra data cache misses to kill any advantage, even in
a highly-optimized inner loop.
For 8-bit integets, a quick solution is:
int
round_up(int x)
{
if (x 0xf0) {
if (x 0xc0)
return (x 0x80) ? 0x80 : 0x40;
else {
return (x 0x20) ? 0x20 : 0x10;
}
}
else {
if (x 0xc)
return (x 0x8) ? 0x8 : 0x4;
else {
return (x 0x2) ? 0x2 : 0x1;
}
}
}
It's actually faster than the BSF/BSR operations on Pentium (and the
ffs() libc function), as Pentium does a sequential search of the bit
string and therefore is O(n) (eek!)
The innermost comparison could probably be avoided if it wasn't 00:37
or if I didn't have to get up early in the morning. You could also
combine that with a smaller lookup table to get the best of both
worlds.
Patryk.
To Unsubscribe: send mail to majord...@freebsd.org
with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
At Sat, 21 Aug 1999 12:54:32 +0200, Nick Hibma wrote:
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3- 2
4,5,6,7- 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
This small prog works at least on x86
=
#include sys/types.h
#include machine/cpufunc.h
int
main(int argc, char **argv){
int i, j, k;
sscanf(argv[1], %d, i);
j = 1(fls(i)-1);
k = 1(fls(i-1));
printf(%d %d %d\n, j, i, k);
return 0;
}
=
/Johan K
To Unsubscribe: send mail to majord...@freebsd.org
with unsubscribe freebsd-hackers in the body of the message
RE: from number to power of two
On 21-Aug-99 Nick Hibma wrote:
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3 - 2
4,5,6,7 - 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
a bit of fiddling around gives:
int pw2(register unsigned i) {
register unsigned cnt=1;
do {
i = 1;
cnt =1;
/* printf([%x %x],,i, cnt); */
} while (i);
/* return(cnt) /* higher */
return( cnt 1); /* in bound */
/* return(cnt 2); /* lower */
}
Prolly should do boundry check for case 0 : 0 - 0 ? 0 - 1.
Regards,
---
Don Read dr...@calcasieu.com
EDP Manager dr...@texas.net
Calcasieu Lumber Co. Austin TX
-- But I'm in good company, sendmail has kicked a great many
butts in the past
To Unsubscribe: send mail to majord...@freebsd.org
with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
In message pine.bsf.4.10.9908211250310.7595-100...@heidi.plazza.it Nick Hibma writes: : Does anyone know an inexpensive algorithm (O(1)) to go from an number to : the next (lower or higher) power of two. 1 ffs(x) Warner To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-hackers in the body of the message
Re: from number to power of two
Nick Hibma scribbled this message on Aug 21:
Does anyone know an inexpensive algorithm (O(1)) to go from an number to
the next (lower or higher) power of two.
1 - 1
2,3 - 2
4,5,6,7 - 4
8,9,10,11,12,13,14,15 - 8
etc.
So %1101 should become either %1 or %1000.
The only solution I have so far is a table. That is a possibility as the
the highest number will be 32 I think.
hmmm how about:
int
fls(int n)
{
/* courtesy of fortune, of course this is O(lgn) */
/* swap the bits around */
n = ((n 1) 0x) | ((n 1) 0x);
n = ((n 2) 0x) | ((n 2) 0x);
n = ((n 4) 0x0f0f0f0f) | ((n 4) 0xf0f0f0f0);
n = ((n 8) 0x00ff00ff) | ((n 8) 0xff00ff00);
n = ((n 16) 0x) | ((n 16) 0x);
/* mask all but the lowest bit off */
n = n -n;
/* swap them back to where they were originally */
n = ((n 1) 0x) | ((n 1) 0x);
n = ((n 2) 0x) | ((n 2) 0x);
n = ((n 4) 0x0f0f0f0f) | ((n 4) 0xf0f0f0f0);
n = ((n 8) 0x00ff00ff) | ((n 8) 0xff00ff00);
n = ((n 16) 0x) | ((n 16) 0x);
return n;
}
now this is O(lgn) (where n is number of bits in an int), but I'm not
sure how this will perform wrt the other posting.. it probably won't be
that fast because of all the arithmetic that happens, and a binary search
of the number would probably be faster (which I have implemented a few
times)...
--
John-Mark Gurney Voice: +1 541 684 8449
Cu Networking P.O. Box 5693, 97405
The soul contains in itself the event that shall presently befall it.
The event is only the actualizing of its thought. -- Ralph Waldo Emerson
To Unsubscribe: send mail to majord...@freebsd.org
with unsubscribe freebsd-hackers in the body of the message
