Challenge: NextPower2 for LongInt

[jdarling]

Ok, since when I asked about NextPower2 I got so many answers, and everyone seemed to have fun. Lets try a little challenge.

Create the fastest cross platform implementation of NextPower2 that takes and returns a LongInt.

EX:
[pascal]function NextPow2(aVal : LongInt) : LongInt;
begin
if aVal >= (1 shl 31) then
begin
result := 1 shl 31;
exit;
end;
result := 1;
while result < aVal do
result := result shl 1;
end;[/pascal]

Rules:
* Must compile in FPC for Windows, Linux, and Mac
* You can't simply extend cairnswm fixed lookup table method, as this will always be the fastest possible, and eventually memory comes into concern.

Anyone interested?

I haven't thought of a benchmark or anything just yet, any suggestions?

PS: I think that if there is interest in this sort of thing, then WILL or Dom should create a place for us to post the winning code snippets for when people ask how to do something quickly

[Nitrogen]

Why not try something other than Power of 2...
Try to pick an algorithm that, while simple, needs to be run many number of times...

[jdarling]

Why not try something other than Power of 2...
Try to pick an algorithm that, while simple, needs to be run many number of times...

Actually, I have a few in mind, but I thought this would be a good start since its a common need and we only solved for an integer.

[dmantione]

Well, all methods except the lookup table can be used for longint as well?

[Mirage]

[pascal]
function NextPowerOf2(x: Longint): Longint;
begin
Result := x-1;
Result := Result or Result shr 1;
Result := Result or Result shr 2;
Result := Result or Result shr 4;
Result := Result or Result shr 8;
Result := Result or Result shr 16;
Inc(Result);
end;
[/pascal]

upd: tags corrected

[cairnswm]

I really like the idea of these code offs - my problem is that I just dont work at a low enough level! All my solutions will be working out the best/quickest method using only high level Pascal code (like the lookup solution).

[JSoftware]

isn't a longint the same as an integer?

[dmantione]

Well, in Delphi this is true. In FPC it depends on the compiler mode. In modes objfpc and delphi it is the same as longint. In modes fpc, tp, macpas and it is the same as smallint.

But, for all proposed solutions except the table lookup, it doesn't matter wether the integer is 16 or 32 bits.

[Nitrogen]

I really like the idea of these code offs - my problem is that I just dont work at a low enough level! All my solutions will be working out the best/quickest method using only high level Pascal code (like the lookup solution).

As we've seen, sometimes those can be better than an assembler rountine...