in reply to Loops loosing Performance
What you have here is the classical "bit counting problem". By ANDing the two numbers all you need is find the amount of 1s in the result. The bit counting problem is a terrific example of the tradeoffs between space and time efficiency, and is one my my favorite interview questions.
You can find a lot of info about it online, for example here.
To make a long story short, the fastest technique is table lookup. Precompute the counts for all bytes (256 of them) in a table and do a simple lookup to find results later.
What you've been shown by kaif and others are the more arcane and enjoyable methods, but table lookup will be faster.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Loops loosing Performance
by kaif (Friar) on Jun 10, 2005 at 07:16 UTC |
In Section
Seekers of Perl Wisdom