Doshi's blog

Thème:

Bidouiller du binaire en Ruby

, — ~5mn de lecture

Disclaimer : Oui, évidemment, Ruby c’est pas le meilleur langage pour faire ça, je sais, merci (vous allez voir une des raisons plus loin dans le billet). Mais c’est le langage que je connais le mieux, et juste pour une petite question que je me posais, j’avais pas envie de passer du temps à chercher comment on fait en Haskell, en Python, ou autre.

Tantôt, je lisais tranquillou ce billet de blog de Eli Bendersky, sur un algorithme rapide (≃ O(log n))qui permet de calculer le reste d’une division. À la fin, il transcrit le code en Python comme suit :

def fast_remainder(a, b):
    if a < b: return a
    if a - b < b: return a - b
    r = fast_remainder(a, b + b)
    if r < b: return r
    return r - b

Vous voyez ce r = fast_remainder(a, b + b) ? Le b+b là.
Vu que le principe de l’algorithme est d’être rapide, je me suis posé la question : « Mais du coup. Théoriquement, ça serait plus rapide de faire b+b ou b×2 ? » 1

b+b ou b×2, that is the question

Du coup, c’est là que j’ai sorti Ruby.

Alors, comment on voit des chiffres en binaire en Ruby, pour commencer ? C’est facile, c’est avec Integer.to_s(base). Donc pour représenter des nombres en base 2 :

42.to_s(2) #=> "101010" (pas mal, hein ?)

Et dans l’autre sens, on peut pas faire 101010.to_s(10). Bah oui, 101010, c’est déjà en décimal donc Ruby va juste nous transformer 101010 en décimal vers sa représentation en décimal, donc… 101010. On s’emmerde un peu.

Sauf que Ruby a des représentations pour le binaire. Suffit de rajouter le préfixe 0b2.

0b101010 #=> 42

Et du coup, regardons la représentation binaire du double de 42 : 84

42.to_s(2) * 2 #=> "101010101010"

Et là si vous êtes un tantinet attentifs, vous remarquerez que 0b101010101010, ça fait un peu beaucoup pour 84. Et vous aurez bien raison, parce que ça fait 2730.

« Mais qu’est-ce qu’il s’est passé ? » : petite parenthèse

Si vous êtes familier avec Ruby ou Python (il fait pareil le coquin), vous savez probablement déjà ce qu’il s’est passé, donc vous pouvez passer cette partie

Faisons une petite parenthèse sur les types et les opérateurs en Ruby. Bon.

Ce qu’il s’est passé, c’est que l’opérateur * il a un sens différent suivant le type avec lequel on l’utilise.
Il y a une méthode * pour le type Integer, et une méthode * pour le type String Avec des nombres (donc la fonction Integer.*), ce sera la multiplication qu’on connait tous

42 * 2 #=> 84

MAIS Avec une chaine de caractères str (donc la fonction String.*), ça veut dire “Fais moi n copies de la chaine str stp”. Donc :

  "Salut" * 3 #=> "SalutSalutSalut"
#  ^ str    ^ n

Donc maintenant qu’on sait ça, on peut remarquer un truc : quand on faisait 42.to_s(2), on convertissait 42 en String ! Et du coup, on appelait la fonction String.* !

42.to_s(2) * 2 => "101010" * 2 => "101010101010"

Fin de la parenthèse

Bon et du coup, nous on voulait avoir 84 en binaire, comment qu’on fait ?

Tout simplement

84.to_s(2) #=> "1010100"

ou, avec le calcul apparent

(42 * 2).to_s(2)

Bon. C’était quoi la question déjà. “b+b ou b*2

J’vais répondre vite fait et ensuite j’vais vous parler de deux ou trois autres trucs à faire en binaire avec Ruby en vrac

Donc. Je rappelle qu’on est en binaire. En base 2. Si on fait l’analogie avec le décimal, multiplier par 2, c’est l’équivalent de multiplier par 10.

« Hey mais attends c’est super facile de multiplier par 10, suffit de rajouter un 0 à la fin ! »

Et voilà, t’as tout compris

Multiplier par 2, ça revient à rajouter un 0 à la fin, donc de décaler les bits vers la gauche de 1 rang.

Ça tombe bien y’a un opérateur pour ça en Ruby (et en Python, en Java, en C, …) : Integer.<<3
Du coup quand on fait a << b, ça décale a (en binaire) de b bits. Et concrètement ça multiplie a par 2^b
Et du coup évidemment y’a l’opérateur inverse : >>, qui fait… l’inverse…

Sinon, y’a les opérateurs :

Eeeeeeeet j’ai plus rien à dire

Salut

  1. Oui, je sais, c’est débile, c’est du code Python, c’est pareil de toute façon. Je sais mais laissez moi me poser des questions théoriques intéressantes, non mais oh. 

  2. Même en plus général, on utilise souvent le préfixe 0b devant un nombre pour dire que c’est en binaire. On trouve aussi 0x pour l’hexadécimal (base 16) et 0o pour l’octal (base 8). En maths, on pourrait aussi mettre respectivement un ₂, un ₁₆ ou un ₈ après le nombre pour indiquer sa base. 

  3. Je précise Integer parce que cet opérateur existe aussi pour : IO, CSV, Set, Date et d’autres. La plupart du temps on l’utilise avec Array, mais il a plus du tout le même sens que pour Integer, donc c’est pas la question. 


Il n'y a pas de commentaires sur ce blog, cependant, n'hésitez pas à me faire des remarques sur cet article (ou autre, d'ailleurs). Que ce soit via Mastodon, Twitter, XMPP ou encore par mail, je serai ravi de voir que des gens me lisent pour de vrai