Преобразование степеней 2 в линейную последовательность без логарифмов

Question

Без использования логарифмов, как я могу преобразовать последовательность степеней 2 в линейные целые числа в 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. Также обратите внимание, что вы всегда можете получить мощность двух по длине строки, созданной алгоритмом выше. Например, длина строки «1001010» равна 7, что означает, что число находится между 64 и 127.

Answer 2

Это преобразование Visual Basic в алгоритм C# дальше. Это целочисленная функция 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]); 
     } 
    } 
}