algorithm - 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

是的，您将数字转换为二进制。例如，64 的二进制值是：1000000。由于 1 在第七位，因此您知道所需的值是 7。这是一个 Visual Basic 程序来执行此操作：

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

在此算法中，值被附加到字符串中，但您也可以将它们存储在 1 和 0 的数组中。另请注意，您始终可以通过上述算法生成的字符串的长度来获得 2 的幂。例如，字符串“1001010”的长度为 7，表示该数字介于 64 和 127 之间。

Answer 2

这是 C# 算法进一步向下的 Visual Basic 转换。这是一个整数 Log2 函数。它使用先前初始化的数组。这个（和许多其他的小技巧）可以在这里找到：http: //graphics.stanford.edu/~seander/bithacks.html

这个算法的优点，以及为什么它很快，是因为它执行以 2 为底的对数，只需要几个简单的算术运算和数组查找。

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

这是原始的 c# 代码。它是我前段时间制作的一个更大的 BitHelper 类的一个子集。

/// <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]);
        }
    }
}