This is probably the simplest useful assembler routine you will ever come across:

        * Integer Log base 2 *)
        function IntLog2 Value: integer ): integer;
        asm
           BSR EAX, EAX
        end;

Of course, you might want to do some error checking. This version throws EInvalidOp when zero is passed as a parameter:

        (* Integer Log base 2 with error checking *)
        function IntLog2( Value: integer ): integer;
        const TExceptClass: TClass = EInvalidOp;
              Msg: string = 'Invalid input to logarithm function.';
        asm
           CMP EAX, 0
           JG @@Ok

           MOV DL,1
           MOV EAX, TExceptClass
           MOV ECX, Msg
           CALL Exception.Create
           CALL System.@RaiseExcept

           RET
        @@Ok:
           BSR EAX, EAX
        end;

Delphi does have a Log2() function, which uses x86 floating-point instructions. Our function provides the equivalent of: Trunc(Log2(SomeInteger)). But this involves a parameter conversion, since Log2() takes extended as a parameter, and an extra call to Trunc().  IntLog2 is about eight times faster.

How does the function work?  It relies on the fact that a number written in any base is simply a sum of consecutive powers.  Consider that for any number written in base B with n digits d_n..d₀, then its value is the sum of d_nBⁿ..d₀B⁰.  For example, in base 10, a number such as 12,345 is:

Value = 1·10⁴ + 2·10³ + 3·10² + 4·10¹ + 5·10⁰ = 12,345₁₀

And in binary:

Value = 1·2¹³+ 1·2¹²+ 0·2¹¹+ 0·2¹⁰+ 0·2⁹+ 0·2⁸+ 0·2⁷+ 0·2⁶+ 1·2⁵+ 1·2⁴+ 1·2³+ 0·2²+ 0·2¹+ 1·2⁰ = 12,345₁₀

Take a look at the leftmost factor, which is the product of the digit at that position with the base, raised to its corresponding power.  The power at this position is equal to Trunc(Log_Base(Value)), which is also the digit's (0-numbered) position.  So to compute Trunc(Log_Base(Value)), we somehow need to find this factor. In our case, we need to find the number of digits when an integer is written in base 2.  But since the leftmost digit in binary can only be 1, we only need to find the number of digits the number would have when written in base 2.   Luckily, our hardware already represents integers in binary, so we simply need to count the number of binary digits.  However, since our hardware uses fix-length memory locations and registers (eg, 16, 32, 64 bits), we actually need to find the position of the highest set bit within a register or memory location.

You might scan for the first set bit in EAX using:

        function IntLog2( Value: integer ): integer;
        asm
           MOV ECX, 32

        @@loop:
           SHL EAX, 1
           JC @@getout
           LOOP @@loop

        @@getout:
           MOV EAX, ECX
           DEC EAX
        end;

But as we saw earlier, the Intel processor family provides a shortcut, in the form of the BSR instruction. Its format is: [BSR src, dest].  It scans src for the position of the highest set bit, counted from the rightmost (lowest) bit and stores the result in dest.  Why EAX?  With Delphi's register calling convention (the default), a 32-bit integer parameter and integer function result are both stored in EAX.  This feature, which is not present in other RAD tools (and not guaranteed on C++ compilers) allows the function to be just one assembly instruction long.

 

Download
A unit containing the 2 versions can be downloaded as a zip file here.