Doshi's blog

Bidouiller du binaire en Ruby

31/05/2018 — ruby, informatique, programmation — ~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 ? » ¹

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 0b ².

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.

42 * 2 #=> 84

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

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

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.<< ³
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 :

• & : ET bit à bit
• | : OU bit à bit
• ^ : OU EXCLUSIF bit à bit
• ~ : Complément à 1. Sauf que ça fait des trucs chelous et que je me rappelle plus comment ça marche

Eeeeeeeet j’ai plus rien à dire

Salut