2

Does anyone know of an algorithm similar to De Bruijn's LSB, but for MSB? Or alternately the most efficient way of determining the MSB?

I know Log_2(Val) will do this, but I don't know if it's the most efficient method.

The reason I need it is I need to convert little-endian to big-endian. I know the standard algorithm for this. However, the input is 64 bit, but typically the numbers will be 16 or 24 bit, so swapping the whole 8 bytes around is unneeded 99.9% of the time.

IamIC
  • 17,747
  • 20
  • 91
  • 154
  • 1
    Is http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c helpful? – Jeff Foster Mar 16 '11 at 13:45
  • I'd be surprised if special-casing this kind of thing would give a performance win - byte swapping is only a few instructions, so adding a few more instructions to test for special cases may well be counter-productive, particularly if you have branching. – Paul R Mar 16 '11 at 13:47
  • @Jeff that is helpful, thanks. @Paul, you could be right. However, I also have the need of knowing how many bytes to process. – IamIC Mar 16 '11 at 13:56
  • I'm thinking a simple loop: test with AND, << test by 8 pattern will work. – IamIC Mar 16 '11 at 14:28

2 Answers2

2

Isn't this exactly http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn ?

AShelly
  • 34,686
  • 15
  • 91
  • 152
1

If you want a fast method and are able/willing to use hardware specific instructions, you should take a look at x86 BSR (Bit Scan Reverse) or similar instruction.

Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand).

xor edx, edx
mov eax, 0x12345678
bsr edx, eax

It should store 28 in edx (bit 28 is the MSB). edx would be unchanged if no MSB is found.

bkausbk
  • 2,740
  • 1
  • 36
  • 52