Casse-tête binaire


Je viens d’inventer le problème suivant, qui est en fait une variation informatique d’un casse-tête récemment proposé sur un autre blog membre du C@fé des Sciences.

Un registre de microprocesseur contient un mot de 32 bits quelconque, mais dont exactement 8 bits sont à 1, les autres à 0 (par exemple 01001000000000111000010000101000)

Comment faire pour modifier les premiers 8 bits du mots de façon à ce qu’ils comportent autant de bits à ‘1’ qu’il n’y en a au total dans les 24 bits suivant (soit 6 dans l’exemple ci-dessus), et ceci en une seule instruction du processeur ?

Binary Kite par Syntopia

"Binary Kite" par Syntopia

Si vous n’êtes pas familier avec l’assembleur, disons que vous disposez des mêmes opérations qu’une calculatrice, mais en binaire : addition, soustraction, ansi que des fonctions logiques (et, ou, …). Une instruction, c’est une de ces opérations suivie d’une opérande.

  • LA REPONSE EST XOR #11111111000000000000000000000000
    en effet, le premier octet contient 8-n ‘0’, où n est le nombre de bits à 1 dans les 3 octets suivants. Il suffit donc d’inverser les 8 bits pour obtenir n ‘1’…

    le problème d’origine est l’excellente “Petite Enigme” du Webinet des Curiosités. C’est énervant ces petits problèmes impossibles qui ont une solution toute bête, n’est-ce pas ?

  • Moi j’ai “trouvé”. J’ai justement lu la solution sur le site en question il y a peu. ^^
    Je pensais pas que ça fonctionnerais, mais si lol
    Je laisse donc les autres lecteurs chercher, sauf si on me demande le contraire, bien sûr…

    PS: Certains ne nous disent pas tout, hein… 😀

  • Voilà, mes collègues ont tous trouvé, mais je les ai un peu aidés en leur disant que ce problème est dérivé de la “petite enigme” suivante: on a 64 pions de Reversi (ou Othello) dont 10 ont la face noire visible, et donc 54 sont blancs. Les yeux bandés, il faut répartir les pièces en deux tas (pas forcément égaux) tels qu’il y ait le même nombre de pièces noires dans les deux tas.

    (je ne fais pas encore le lien vers ce site car la solution qui y figure aide trop à résoudre ce problème-ci, mais je ferai le lien demain, promis)

    Alors, personne n’a de solution ?

  • le premier à avoir trouvé la solution, c’est mon collègue Pierre-Alain. Bravo !. Mais bon, je l’ai un peu aidé, c’est vrai …