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

はい、数値を 2 進数に変換します。たとえば、64 のバイナリ値は 1000000 です。1 は 7 番目の位置にあるため、必要な値は 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]);
        }
    }
}