Determining the position of the highest set bit?

[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: Select all

for (count=32; bits; bits>>=1)
	count--;

That is, shifting the value to be examined until it vanishes and counting the necessary steps.

Any ideas?
x86 assembler welcome again.

[Kemper_Boyd]

The BSR Bit Scan Reverse instruction?

These links might also be useful.
http://graphics.stanford.edu/~seander/bithacks.html
http://www.ciphersbyritter.com/NEWS4/BITCT.HTM

[venusian]

The x86 has some instructions for bit manipulation - I don't do x86 myself but it'll be worthing check that there isn't an instructions to do exactly this.

What do you want the top bit for? If you're planning on clearing, or setting, it then there are quick ways of doing this using xor and increment by one.

Otherwise, I think the quickest way would be an unrolled binary search as below. If there's some pattern to your data you may be able to produce a version better optimised for your app.

Code: Select all

int highbit( int val )
{
	int bitnum=0;
	if( val&0xffff0000 )
	{
		bitnum += 16;
		val>>=16;
	}
	if( val&0xff00 )
	{
		bitnum += 8;
		val>>=8;
	}
	if( val&0xf0 )
	{
		bitnum += 4;
		val>>=4;
	}
	if( val&0xc )
	{
		bitnum += 2;
		val>>2;
	}
	if( val&0x2 )
	{
		bitnum +=1;
	}

	return( bitnum );
}

[SpicyTaco]

BSR r32, r/m32

r/m32 = operand to test for highest bit.
r32 = register that receives the result.

Smaller than this will be hard (two bytes), faster may be possible as the instruction takes 7 to 104 cycles. This is according to my i486 manual, so current processors may have a faster implementation. If there is a faster way then I guess it would involve halving your search space instead of doing a linear search which your code as well as the BSR instruction does (only then in microcode).

For example:
if (a<0x00010000)
{
// bits 16-32 are clear, so only bits 0-15 to test.
if (a<0x00000100)
...
else
...
}
else
{
// At least one of the bits 16-32 are set.
if (a<0x01000000)
...
else
...
}

However, you would end up with quite a number of instructions, which would eat up your cache. And you have at least 8 jumps. So while the search strategy is faster, the one instruction version may still be faster.

[Kemper_Boyd]

BSR is a micro coded loop on older chips and
a binary search on Athlon and P4, I think P6
may be faster still (in cycles). I'd be surprised
if there's anything better, though I won't bet on it,
damn crypto people and their sneaky tricks!

[pogo]

I recommend you buy borrow or steal a copy of Hacker's Delight (us uk): it has four pages on this, with seven full listings, based on a binary search like that posted by venusian, the last two branch free. Too much for me to post, and as this is only a small fraction of the book (four of almost 300 pages) it's worth tracking down for it's in-depth coverage of pretty much every technique like this.

[Firefox]

I recommend you buy borrow or steal a copy of Hacker's Delight (us uk):

Cor, thanks pogo!

The book has its own website:

http://www.hackersdelight.org/

... which contains some samples from the book in PDF form. I was so impressed after reading them that I immediately went and chucked a copy in my Amazon shopping basket!

The website also has some stuff not in the book that's in a similar vein, and some very nice links too.

[Dvorak]

Wow. So much input. So much to explore.
Thank you, guys.

It's like in the old days, when each and every economised cycle had instant impact on the performance. If I'll ever reach something like realtime with my raytracer (which still is around 6 fps) , I'll add you to the credits list...

[piku]

Well, I knew I was going to buy something from Amazon today...

Looks like a book to sit next to my K&R C book.

[Istar]

Well unless I've got the wrong end of the stick here, isn't it going to be easier to do a series of straight decimal checks?

Example for an 8-bit byte:

If testvalue > 127
bit8_is_set
ELSEIF testvalue > 63
bit7_is_set
ELSEIF testvalue > 31
bit6_is_set
ELSEIF testvalue > 15
bit5_is_set
ELSEIF testvalue > 7
bit4_is_set
ELSEIF testvalue > 3
bit3_is_set
ELSEIF testvalue > 1
bit2_is_set
ELSEIF testvalue = 1
bit1_is_set
ELSE
no_bits_set
ENDIF

You could of course write this as a loop, rather than unrolled:

FOR loop = 7 to 0 STEP -1
IF testbyte > ((2 ^ loop) - 1) THEN RETURN (loop + 1)
NEXT
RETURN 0

This returns the absolute bit number of the highest set bit in testbyte.

I.

[Kemper_Boyd]

BSR is a binary search on modern processors, and microcoded
too, so it should be optimal. Writing your own is almost guaranteed
to be slower, unless you have some tricks based upon the
distribution of the numbers being tested. Reading up on the
topic it appears the only faster methods rely on support
for instructions like popcount and associated micro-architecture.

So BSR for modern processors, your own binary search for
older ones. Unless someone knows otherwise?

*googles*

The Pentium and K6 use micro-coded loops.
Athlon and Pentium 4 use a binary search, but it's still 8-10 clocks. A
2-cycle popcount would give a 4-cycle bsf. If a bit-reverse instruction were
also added, bsr could be emulated in 6-cycles.

IA64 may well do this, the new versions have extended
support for popcount, probably to keep a very big but
quiet customer happy.

[Riff]

The fact that BSR is microcoded is a bad thing, not a good thing. Microcoded instructions are easily outclassed by longer instruction streams that execute non-microcoded instructions.

I use the following routine to calculate the most significant bit of a word, as defined by the Nuon (Aries) MSB instruction: if the word is 0 or -1, the returned value is 0, otherwise, if the word is positive, the returned value is the bit position of the most significant 1 bit plus one and if the word is negative, the returned value is the bit position of the most significant 0 bit plus one. The definition of most-significant in this case is the bit position of the 1 (0) bit in the leftmost instance of the pattern [01]b ([10]b) in a twos complement representation of a positive (negative) number. Note that the MSB return behvior differs for negative numbers, particularly for powers of two. This almost never matters as MSB is most frequently used for floating point normalization of two floating point values and for speeding up floating point division. Almost all software floating point routines convert to positive operands and apply the sign fix-up afterwards.

Code: Select all

uint32 MSB(int32 n)
{
  uint32 sigbits;

  if((n == 0) || (n == -1))
  {
    sigbits = 0;
  }
  else
  {
    //n = n if positive, n = ~n if negative
    n = (n ^ (n >> 31));

    //fold n into itself to get a new value where all bits below the
    //most significant one bit have also been set to one.

    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >> 16);

    //get the ones count

    n -= ((n >> 1) & 0x55555555);
    n = (((n >> 2) & 0x33333333) + (n & 0x33333333));
    n = (((n >> 4) + n) & 0x0f0f0f0f);
    n += (n >> 8);
    n += (n >> 16);

    //return the ones count... if n was orignally 0 or -1 then the ones count
    //will be zero which is exactly what we want
    sigbits = ((uint32)n) & 0x1FUL;
  }
  return sigbits;
}

This function is a combination of the "Most Significant 1 Bit" and "Population Count" algorithms taken from the Aggregate Magic Algorithms page at http://aggregate.org. There is a slight difference in the code where the two routines are joined together. Also note that the first check for 0 and -1 is not strictly necessary as the end result will be 0 even if the check is left out. It may end up being more costly to perform the check than to skip the number crunching in which case the code should be modified to always take the second path. Similarly, if support for negative numbers is not needed, the first line in the second path can be eliminated.

The first part of the code modifies the original word such that all bits prior to the most significant one bit are set to one, e.g. 0x05A3 -> 0x07FF. The second half of the code gets the Ones Count of the intermediate result, which is equal to the bit position of the most significant bit plus one.

The reason that this algorithm is much faster on most modern architectures is because all of the operations are simple adds, shifts and ors, which are all likely to be very fast one-cycle instructions. More importantly, there are no branches in the code. This ensures that there are no branch mispredictions or associated cache flushes. Finally, this algorithm is essentially replacing searches with parallel binary comparisons which are exploited via boolean operations. The fastest hardware BSR instructions would likely want to implement this method in hardware.

[Kemper_Boyd]

*bump* Only just seen this.

Code: Select all

uint32 MSB(int32 n)
{
  uint32 sigbits;

  if((n == 0) || (n == -1))
  {
    sigbits = 0;
  }
  else
  {
    //n = n if positive, n = ~n if negative
    n = (n ^ (n >> 31));

    //fold n into itself to get a new value where all bits below the
    //most significant one bit have also been set to one.

    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >> 16);

    //get the ones count

    n -= ((n >> 1) & 0x55555555);
    n = (((n >> 2) & 0x33333333) + (n & 0x33333333));
    n = (((n >> 4) + n) & 0x0f0f0f0f);
    n += (n >> 8);
    n += (n >> 16);

    //return the ones count... if n was orignally 0 or -1 then the ones count
    //will be zero which is exactly what we want
    sigbits = ((uint32)n) & 0x1FUL;
  }
  return sigbits;
}

Maybe I'm being stupid here but is your code really faster than
4, 6 or 8-10 cycles? It may prove useful in some cases, but there
appear to be cases where your code would likely be much slower.
If I've got the wrong end-of-the-stick please correct me.

*googles*

The Pentium and K6 use micro-coded loops.
Athlon and Pentium 4 use a binary search, but it's still 8-10 clocks.
A 2-cycle popcount would give a 4-cycle bsf. If a bit-reverse instruction were also added, bsr could be emulated in 6-cycles.

IA64 may well do this, the new versions have extended
support for popcount, probably to keep a very big but
quiet customer happy.

[hairy_pete]

bsr/bsf is the shortest method of doing this. It isn't fast though.

Alternatively, you can do something like this:

Code: Select all

mov cx, 32
@@:
rol eax, 1
loopnc @b

That'll come out CY and CX==bitposition for the highest set bit, or NC for EAX==0. It destroys EAX though.

[Dio]

Big problem with that is that if the highest bit set hasn't a usual value, or is usually more than 4 bits down, then you'll get at least one branch misprediction. A mispredict costs more than one bitscan instruction, guaranteed.

If it saves a branch, use it, but if it doesn't, it's probably faster without.