What's the fastest way to enumerate through an integer and return the exponent of each bit that is turned on? Have seen an example using << and another using Math.Pow. Wondering if there is anything else that's really fast.
Thanks.
-
2In my own experience Math.Pow is very very slow. Much slower than even, say, Math.Cos or Math.Sqrt. It has no chance to outperform integer shifts, ever.Roman Starkov– Roman Starkov2009-10-06 11:50:26 +00:00Commented Oct 6, 2009 at 11:50
Add a comment
|
8 Answers
The fastest way? Lookup tables are almost always the fastest way. Build an int[][] array with four billion entries, one for each int, containing an array of the numbers you want. Initializing the table will take some time, of course but the lookups will be incredibly fast.
I note that you have not said what "fastest" means with sufficient precision for anyone to actually answer the question. Does it mean fastest amortized time including startup time, or marginal lookup time assuming that startup costs can be neglected? My solution sketch assumes the latter.
Obviously a 32 bit machine with 2 billion bytes of address space will not have enough address space to store thirty billion bytes of arrays. Get yourself a 64 bit machine. You'll need at least that much physical memory installed as well if you want it to be fast -- the paging is going to kill you otherwise.
I sure hope the couple of nanoseconds you save on every lookup are worth buying all that extra hardware. Or maybe you don't actually want the fastest way?
:-)
7 Comments
Blorgbeard
What are you, comicbook guy? Obviously, he wanted the fastest reasonable method.
Eric Lippert
Then someone needs to define "reasonable". Once you define "reasonable", you have a performance specification. "Fastest possible" is not a specification. By thinking about what the costs are of the fastest possible implementation, you start to realize that performance is not ever about "fastest possible". It's about obtaining a reasonable performance return on an investment. Performance tuning is expensive; without a realistic spec, you can spend a lot of money trying to reach a level of performance you don't actually need.
Accipitridae
Huge lookup tables are quite frequently not the fastest way to implement stuff. Since we almost certainly get a cache miss a lookup will need in the order of hundred(s) of cycles. Any of the other proposed methods beats that easily.
Brian
@Majkara Tito: HIs lookup table won't hammer RAM if he builds the lookup table in hardware.
|
I imagine bit-shifting would be the fastest. Untested, but I think the following ought to be fast (as fast as IEnumerables are at least).
IEnumerable<int> GetExponents(Int32 value)
{
for(int i=0; i<32; i++)
{
if(value & 1)
yield return i;
value >>= 1;
}
}
If you want it to be faster, you might consider returning a List<int> instead.
7 Comments
lc.
I'm not exactly sure what you mean by int32Value but in order to use the ForEach extension method, you have to have an IList. You can call ToList() on an IEnumerable to get one if you'd like. And if you want, you can make the above code an extension method and call myInt.GetExponents().ToList().ForEach(...)
leppie
You can try aggregate in linq.
LukeH
Shouldn't your loop start at zero? ie, The first bit represents exponent 0, the second bit represents exponent 1 and so on. (2^0 = 1, 2^1 = 2, 2^2 = 4 etc).
lc.
Right...and that would be me overthinking the problem on not enough sleep. Fixed.
Ray
The line
if (value & 1) doesn't work, "Cannot convert int to bool", so I wrote if ((value & 1) == 1). |
The IEnumerable is not going to perform. Optimization of some examples in this topic:
First one (fastest - 2.35 seconds for 10M runs, range 1..10M):
static uint[] MulDeBruijnBitPos = new uint[32]
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
static uint[] GetExponents(uint value)
{
uint[] data = new uint[32];
int enabledBitCounter = 0;
while (value != 0)
{
uint m = (value & (0 - value));
value ^= m;
data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27];
}
Array.Resize<uint>(ref data, enabledBitCounter);
return data;
}
Another version (second fastest - 3 seconds for 10M runs, range 1..10M):
static uint[] GetExponents(uint value)
{
uint[] data = new uint[32];
int enabledBitCounter = 0;
for (uint i = 0; value > 0; ++i)
{
if ((value & 1) == 1)
data[enabledBitCounter++] = i;
value >>= 1;
}
Array.Resize<uint>(ref data, enabledBitCounter);
return data;
}
Comments
A lookup array for one byte's worth of bits ought to be close to the fastest you can do in safe C# code. Shift each of the 4 bytes out of the integer (casting to uint as necessary) and index into the array.
The elements of the lookup array could be an array of exponents, or, depending on what you're doing with the bits, perhaps delegates that do work.
1 Comment
Mike Dunlavey
++ I like this, except that then it becomes an issue of efficiently collecting the results. Each element of the lookup table can be an array of exponents, but then you have to concatenate them, and add 8, 16, and 24 to each array. Not sure how many cycles that would take.
Just for fun, here's a one-liner using LINQ.
It's certainly not the fastest way to do it, although it's not far behind the other answers that use yield and iterator blocks.
int test = 42;
// returns 1, 3, 5
// 2^1 + 2^3 + 2^5
// = 2 + 8 + 32
// = 42
var exponents = Enumerable.Range(0, 32).Where(x => ((test >> x) & 1) == 1);
For a speedier solution I would probably return a plain collection rather than using an iterator block. Something like this:
int test = 2458217;
// returns 0, 3, 5, 6, 9, 15, 16, 18, 21
// 2^0 + 2^3 + 2^5 + 2^6 + 2^9 + 2^15 + 2^16 + 2^18 + 2^21
// = 1 + 8 + 32 + 64 + 512 + 32768 + 65536 + 262144 + 2097152
// = 2458217
var exponents = GetExponents(test);
// ...
public static List<int> GetExponents(int source)
{
List<int> result = new List<int>(32);
for (int i = 0; i < 32; i++)
{
if (((source >> i) & 1) == 1)
{
result.Add(i);
}
}
return result;
}
Comments
Fastest given what distribution for the input? If typically only one bit is set, then this could be faster than looping through looking for set bits.
Taking from the accepted answer for finding the position of the least significant bit, which took from Bit Twiddling Hacks, this solutions loops, finding, clearing and returning the position of each consecutive least-significant-bit.
static int[] MulDeBruijnBitPos = new int[32]
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
static IEnumerable<int> GetExponents(UInt32 v)
{
UInt32 m;
while( v != 0 ) {
m = (v & (UInt32) (-v));
yield return MulDeBruijnBitPos[((UInt32) (m * 0x077CB531U)) >> 27];
v ^= m;
}
}
It only loops as many times as there are bits set.
2 Comments
Sinan Ünür
A far simpler and clearer solution is to use a small (either 16 or 256 entries) lookup table.
Tony Lee
It's really hard to beat lc's answer for simplicity and clarity.
I guess bit shifting (<<) is the fastest.
Comments
If you won't choke on a little C++:
void func(int i, int& n, int a[]){
n = 0;
if (i < 0) a[n++] = 31;
i <<= 1;
if (i < 0) a[n++] = 30;
i <<= 1;
if (i < 0) a[n++] = 29;
i <<= 1;
...
if (i < 0) a[n++] = 0;
}