Determining the position of the highest set bit?

[hairy_pete]

My guess is that a BSF sort of does exactly that in microcode, which inherently would be faster than doing it in macrocode - if only due to the effects you mentioned. Just wanted to demonstrate

[Kemper_Boyd]

My guess is that a BSF sort of does exactly that in microcode, which inherently would be faster than doing it in macrocode - if only due to the effects you mentioned. Just wanted to demonstrate

That's more or less my assertion. Either they use something very fast like
popcount, or they have near optimal uOPs from ROM. There may be
cases other than the general where clever code can still win.

[ehudm]

[quote="Dvorak"]Does anyone know of a fast way of determining the position of the highest set bit in a 32-bit value?
I'm actually using a loop like this:

[code]for (count=32; bits; bits>>=1)
count--;
[/code]
That is, shifting the value to be examined until it vanishes and counting the necessary steps.

Any ideas?
x86 assembler welcome again. [/quote]


The fastiest way is:
if Y = 2^X then:

[code]
[b]
{
X = 0;
if (Y & 0xFFFF0000) X |= 0x10;
if (Y & 0xFF00FF00) X |= 0x08;
if (Y & 0xF0F0F0F0) X |= 0x04;
if (Y & 0xCCCCCCCC) X |= 0x02;
if (Y & 0xAAAAAAAA) X |= 0x01;
}[/b][/code]

Ehud

[tufty]

The fastiest way is:
if Y = 2^X then:

Code: Select all

[b]
{
 X = 0;
 if (Y & 0xFFFF0000) X |= 0x10;
 if (Y & 0xFF00FF00) X |= 0x08;
 if (Y & 0xF0F0F0F0) X |= 0x04;
 if (Y & 0xCCCCCCCC) X |= 0x02;
 if (Y & 0xAAAAAAAA) X |= 0x01;
}[/b]

Ehud

Nice try, and along the right lines. However, you don't deal with the no bits set case.

This does (ripped from some code I wrote a while back).

Code: Select all

	int y = (((x & 0xffff0000) && 1) << 4) |
			(((x & 0xFF00FF00) && 1) << 3) |
			(((x & 0xF0F0F0F0) && 1) << 2) |
			(((x & 0xCCCCCCCC) && 1) << 1) |
			((x & 0xAAAAAAAA) && 1) +
			(x && 1);

Simon

[junkster]

On the PowerPC, you can use the cntlzw instruction (count the number of leading zeros in a word). It's just as fast as any other arithmetic PPC instruction (1 cycle to execute).

[Mr Dom]

The fastiest way is:
if Y = 2^X then:

Code: Select all

[b]
{
 X = 0;
 if (Y & 0xFFFF0000) X |= 0x10;
 if (Y & 0xFF00FF00) X |= 0x08;
 if (Y & 0xF0F0F0F0) X |= 0x04;
 if (Y & 0xCCCCCCCC) X |= 0x02;
 if (Y & 0xAAAAAAAA) X |= 0x01;
}[/b]

Ehud

Nice try, and along the right lines. However, you don't deal with the no bits set case.

This does (ripped from some code I wrote a while back).

Code: Select all

	int y = (((x & 0xffff0000) && 1) << 4) |
			(((x & 0xFF00FF00) && 1) << 3) |
			(((x & 0xF0F0F0F0) && 1) << 2) |
			(((x & 0xCCCCCCCC) && 1) << 1) |
			((x & 0xAAAAAAAA) && 1) +
			(x && 1);

Simon

2nd code will be noticable faster than the 1st method shown...

The first code uses branches (ifs) which will never be the fastest way due to branch prediction misses & the associated pipeline flushes that happen. A problem that gets worse as processors get faster.

The second neatly avoid this because the result of the comparisons are used numerically instead of as a branch.
Taking the snippet: (((x & 0xffff0000) && 1) << 4)
this cunningly avoids the branch, but some compilers may introduce an implicit branch to get the zero bit into a register.
VC doesnt - it (correctly) uses the sbb instruction to achieve that, and produces code that is a mere 27 instruction long with no branches - pretty much as fast as can be. It works out at about 14 cycles with the pentium pipelining too, which is about as long as a single mispredicted branch will take.

Simon =

[venusian]

The second version relies on an undefined language feature. There's no guarantee that boolean true will have bit 0 set. IIRC it's defined only as non-zero.

[Mr Dom]

I think this does the same without using the undocimented features...

Code: Select all

int y =( (((int)((unsigned int)x - 0x0000ffff)>>31) & 16) |
        (((-(int)(x & 0x00ff00ff))>>31) & 8) |
        (((-(int)(x & 0x0F0F0F0F))>>31) & 4) |
        (((-(int)(x & 0x33333333))>>31) & 2) |
        (((-(int)(x & 0x55555555))>>31) & 1) ) ^ 0x1f;
y += (( (int)(x | (-(int)x))>>31) & 1);

It has to calulate the inverse bit pattern then swap it, as the negate trick wont work if the top bit was set. It should work with x being signed or unsigned too ( at least that was the intention )

It is about 2 cycles slower when compiled though.

I just typed it in off the top of my head so apologies for syntax errors & the like