將2的冪轉換爲無對數的線性序列

Question

不使用對數，如何在BASIC中將2的冪的序列轉換爲線性整數？

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