Convert powers of 2 into linear sequence without Logarithms

Question

Without using logarithms, how can I convert a sequence of powers of 2 into linear integers in BASIC?

Input:  0, 1, 2, 4, 8, 16, 32, 64, 128
Output: 0, 1, 2, 3, 4,  5,  6,  7,   8

Answer 1

Yes, you convert the number to binary. For example, the binary value of 64 is: 1000000. Since the 1 is in the seventh position you know the required value is 7. Here is a Visual Basic program to do this:

Public Function DecimalToBinary(DecimalNum As Long) As String
    Dim tmp As String
    Dim n As Long=
    n = DecimalNum
    tmp = Trim(Str(n Mod 2))
    n = n \ 2
    Do While n <> 0
        tmp = Trim(Str(n Mod 2)) & tmp
        n = n \ 2
    Loop
    DecimalToBinary = tmp
End Function

In this algorithm the values are appended to a string but you can just as well store them in an array of 1s and 0s. Also note that you can always get the power of two by the length of the string produced by the algorithm above. For example, the length of the string "1001010" is 7 which means the number is between 64 and 127.

Answer 2

This is a Visual Basic conversion of the c# algorithm further down. It's an integer Log2 function. It uses a previously initialized array. This (and many other bit fiddling hacks) can be found here: http://graphics.stanford.edu/~seander/bithacks.html

The advantage of this algorithm, and why it is fast, is because it performs the base 2 logarithm with nothing more than a couple simple arithmetic operations and an array lookup.

Public Class BitHelper
    ' Methods
    Shared Sub New()
        BitHelper.logTable256(0) = BitHelper.logTable256(1) = 0
        Dim i As Integer
        For i = 2 To 256 - 1
            BitHelper.logTable256(i) = (1 + BitHelper.logTable256((i / 2)))
        Next i
    End Sub

    Public Shared Function Log2(ByVal number As Integer) As Byte
        If (number <= 65535) Then
            If (number > 255) Then
                Return CByte((8 + BitHelper.logTable256((number >> 8))))
            End If
            Return CByte(BitHelper.logTable256(number))
        End If
        If (number <= 16777215) Then
            Return CByte((16 + BitHelper.logTable256((number >> 16))))
        End If
        Return CByte((24 + BitHelper.logTable256((number >> 24))))
    End Function

    Private Shared ReadOnly logTable256 As Integer() = New Integer(256  - 1) {}
End Class

This is the original c# code. It's a subset of a larger BitHelper class I made some time ago.

/// <summary>
/// Helper methods for bit twiddling. Much of the ideas used come
/// from http://graphics.stanford.edu/~seander/bithacks.html
/// </summary>
public static class BitHelper
{
    private static readonly int[] logTable256 = new int[256];

    /// <summary>
    /// Initialize BitHelper class.
    /// </summary>
    static BitHelper()
    {
        logTable256[0] = logTable256[1] = 0;
        for (int i = 2; i < 256; i++) {
            logTable256[i] = 1 + logTable256[i / 2];
        }
    }

    /// <summary>
    /// Determines the integer logarithm base 2 (Floor(Log2(number))) of the specified number.
    /// </summary>
    /// <param name="number">The number for which the base 2 log is desired.</param>
    /// <returns>The base 2 log of the number.</returns>
    public static byte Log2(int number) {
        if (number <= 0xffff) {
            if (number > 0xff) {
                return (byte) (8 + logTable256[number >> 8]);
            } else {
                return (byte) logTable256[number];
            }
        } else if (number <= 0xffffff) {
            return (byte) (16 + logTable256[number >> 16]);
        } else {
            return (byte) (24 + logTable256[number >> 24]);
        }
    }
}