[VB.NET] Compteur en binaire réfléchi (code Gray)

[Skynyrd777]

Bonjour,

Cet algorithme permet de compter en code Gros-Gray (ou binaire réfléchi) ; ce code qui permet d'incrémenter en binaire en ne modifiant qu'un seul bit par itération. Ce code peut être nécessaire dans certains dispositifs électroniques et intéressant dans certains problèmes algorithmiques tels les tours de Hanoï.

Les règles d'incrémentation sont :
- si le nombre de 1 dans le registre est pair, alors inverser le bit de poids faible (le dernier à droite).
- si le nombre de 1 est impair, alors inverser le bit à gauche du 1 le plus à droite. (sinon)

Algorithme en VB.NET

Code:

    Sub Main()

        ' Création du registre
        Dim lgreg As UInteger = 8
        Dim reg As String = ""
        reg = reg.PadLeft(lgreg, "0")
        Dim m As UInteger = 0
        Dim p As UInteger ' position du dernier 1

        ' Compteur itératif
        Do While reg <> "1".PadRight(lgreg, "0")
            Console.Out.WriteLine(reg) ' affichage
            m = 0
            For j As UInteger = 1 To lgreg ' compte les 1
                If Mid(reg, j, 1) = "1" Then
                    m += 1
                    p = j
                End If
            Next j
            ' inversion d'un bit
            If parite(m) Then
                reg = Mid(reg, 1, reg.Length - 1) & (Val(Mid(reg, reg.Length, 1)) Xor 1).ToString
            Else
                reg = Mid(reg, 1, p - 2) & (Val(Mid(reg, p - 1, 1)) Xor 1).ToString & Mid(reg, p, reg.Length)
            End If
        Loop

        Console.Out.WriteLine("1".PadRight(lgreg, "0"))
        Console.In.ReadLine()

    End Sub

    Function parite(ByVal x As Decimal) As Boolean
        Return Not ((x And 1) = 1)
    End Function

Notes : Le code est théoriquement censé revenir à 0 une fois atteint la valeur maximale du registre, ce que cet algorithme ne gère pas. Exemple : sur un registre de 5 bit, 0 se code "00000" en Gray et 31 (2^5-1) se code "10000" (valeur maximale du registre). On modifie la taille du registre dans la variable lgreg dans les déclarations (le registre est initialement à la taille d'un octet).