Misez p'tit Optimisez n°96 : Combien de bits à un dans cet entier ?

[Hobiecat]

Excellent ! Toute la puissance des machines specialisees
Il n'y a pas cette fonction sur les 48/49/50 ?

Oui, la 16C est imparable pour ce genre d'exercice ! La fonction n'existe pas sur 48, mais je ne suis pas sûr sur les 49 et 50.

[bernouilli92]

Des simulateurs de voyager sont dispo ici :
https://stendec.io/ctb/

[cgh]

Excellent ! Toute la puissance des machines specialisees
Il n'y a pas cette fonction sur les 48/49/50 ?

Oui, la 16C est imparable pour ce genre d'exercice ! La fonction n'existe pas sur 48, mais je ne suis pas sûr sur les 49 et 50.

J'avais regarde a tout hasard si le TIprogrammeur LED avait cette fonction, mais non.

[Hobiecat]

Des simulateurs de voyager sont dispo ici :
https://stendec.io/ctb/

Et sur l'excellent Pockemul aussi.

[cgh]

J'ai une autre version en 22 octets (sans le label) sur HP41C sans aucun registre, qui n'utilise que le pile. Qui dit mieux ?

[C.Ret]

Quel dommage qu'il n'y ait pas de x<>0 , x<0 etc. On s'en sort toujours parfois en jonglant comme ici le double test x=0 x>=F pour éviter les doubles GOTO... A part ce défaut je trouve que c'est une série de calculatrices (surtout les 602-603) hyper agréable à utiliser!

Je suis 100% d'accord avec toi, ce son des machines très agréable à utiliser et le manque de tests n'est qu'un défaut mineur et non blocquant car il y a toujours moyen de passer outre avec un jeu plus ou moins enchevêtré de GOTO et LBL.
Je n'ai découvert ces machines que sur le tard, elles sont très pratiques et l'alpha numérique de la fx-602p est très bien intégré et ne fait qu'apporté un plus pour afficher unité, labels en clair etc. Contrairement à l'HP-41C, l'alpha n'alourdi pas l'utilisation très efficace de cette gamme.

Attention, la somme des bits d'un nombre codé en BCD, ça ne donne pas le même résultat ! Pour 182130867283365, je trouve 24 avec le programme ci-dessous en Basic 1000D :

Ah! Oui zut, je suis allé trop vite et j'ai pas pas vu le problème. Autant cela marche avec les bases multiples, hexadécimal, octal , etc du bianire, autant ça ne va pas avec la base décimale.

Bon, j'édite mon précèdent emessage pour indiquer mon erreur.

Code : Tout sélectionner

input n
s$=bin$(n)
t$=change$(s$,"0","","11","1+1","11","1+1")
print val(t$)

Faut que j'analyse cela plus en détail, il doit y avoir de quoi faire de même sur d'autres systèmes qui ont de quoi modifier le contenu des chaines.
Bon, effacer les zéros par "0"→"" ça c'est OK
Mais pourquoi il n'y a que deux fois la substitution des doublons "11" → "1+1", je m'attendais à ce qu'il faille en programmer plus ??
Faut que j'y repense au calme…

Code : Tout sélectionner

001*LBL "MPO96"
002   ∑REG 11
003   CL∑                                                    
004*  LBL 00                                                
005     RCL X  2  ST/ Z  MOD  ∑+  X<>Y  INT  X>0?  GTO 00   
013   RCL 12                                                   
014*END                                                     

Modifications acceptées, c'est comme à l'usine, mieux vaut ajouter quelques équipements pour la sécurité et éviter qu'un des gars soit broyer, écraser ou couper en deux ...
En plus, je n'ai pas vérifié, mais je crois que je me sui trompé de registre , le RCL 12 doit correspondre à ∑x² alors que je voulais renvoyer ∑x
C'est pas grave, 1² fait toujours 1, c'est pas comme si mon opérateur avait eut deux doigts arrachés par la machine ...

Code : Tout sélectionner

10 "A"AREAD A:C=0
20 IF A LET A=A/2:C=C+(A<>INT A):A=INT A:GOTO 20
30 PRINT C

Ah! Oui, c'est presque ce que j'ai sur mon SHARP PC-1211:

Code : Tout sélectionner

1:" "AREAD N:B=0
2:IF NLET N=INT N/2,B=B+(N>INT N:GOTO 2
3:PRINT B

Je laisse la partie fractionnaire dans N avant le test, il y a donc un tours de boucle supplémentaire (et inutile car B n'est pas incrémenté), mais cela fait gagner quelques octets. De toute façon, étant donné la lenteur historique de cet engin, je ne suis pas à un tours de roue près...

Code : Tout sélectionner

LBL 0
#B
RTN

Bon ben voilà cet MPO est terminé, c'est réglé, coupé et emballé...
Je savais bien qu'il y avait un moyen de faire simple, rapide et précis...
Toutes les autres machines ne sont que des traitements de textes, seule l' HP-16C fait de l'arithmétique binaire en vraie !

Mais, encore faut-il avoir placé son HP-16C en mode DEC, il manque donc une instruction à ce programme.

MPO96 - HP-16C no program solution.gif (82.3 Kio) Vu 8494 fois

En plus, il est facile de vérifier que 182130867283365 contient 24 bits à un. Les flèches bleues et la fonction WINDOW permet de vérifier que l'on a bien saisi correctement tous les chiffres de l'entier.

J'ai une autre version en 22 octets (sans le label) sur HP41C sans aucun registre, qui n'utilise que le pile. Qui dit mieux ?

Code : Tout sélectionner

002   0  X<>Y                            ::       :       0       N       1 1 
004*  LBL 00                             ::       :      ∑b      nn       1
005     2  /  ENTER↑ FRC                  :      ∑b    nn/2      .n       1 1 1 1 
009     ST+ Z  ST+ Z -                    :       :    ∑b+b      nn       2 2 1  
012     x>0?  GTO 00                      :       :    ∑b+b      nn       1 2 
014   RDN                                 0       :       :     ∑b"       1 
                                                                         16 octets

Code : Tout sélectionner

002   0  X<>Y                            ::       :       0       N       1 1 
004*  LBL 00                             ::       :      ∑b      nn       1
005     STO Z  2  ST/ T                nn/2      ∑b      nn       2       2 1 2 
008     MOD  +  R↑                     nn/2     nn/2   ∑b+b    nn/2       1 1 1  
011     INT  x>0?  GTO 00                 :       :    ∑b+b       n       1 1 2 
014   RDN                                 0       :       :     ∑b"       1 
                                                                         16 octets

Moins de 22 octets , c'est facile, mes décomptes sont peut-être faux, merci de me le signaler .

[pcscote]

Moins de 22 octets , c'est facile, mes décomptes sont peut-être faux, merci de me le signaler .

Félicitations!
Le compte de 16 octets est bon.
Normalement il faudrait ajouter un label global (min. 5 octets) et le end (3 octets).

[cgh]

J'ai une autre version en 22 octets (sans le label) sur HP41C sans aucun registre, qui n'utilise que le pile. Qui dit mieux ?

Code : Tout sélectionner

002   0  X<>Y                            ::       :       0       N       1 1 
004*  LBL 00                             ::       :      ∑b      nn       1
005     2  /  ENTER↑ FRC                  :      ∑b    nn/2      .n       1 1 1 1 
009     ST+ Z  ST+ Z -                    :       :    ∑b+b      nn       2 2 1  
012     x>0?  GTO 00                      :       :    ∑b+b      nn       1 2 
014   RDN                                 0       :       :     ∑b"       1 
                                                                         16 octets

Code : Tout sélectionner

002   0  X<>Y                            ::       :       0       N       1 1 
004*  LBL 00                             ::       :      ∑b      nn       1
005     STO Z  2  ST/ T                nn/2      ∑b      nn       2       2 1 2 
008     MOD  +  R↑                     nn/2     nn/2   ∑b+b    nn/2       1 1 1  
011     INT  x>0?  GTO 00                 :       :    ∑b+b       n       1 1 2 
014   RDN                                 0       :       :     ∑b"       1 
                                                                         16 octets

Moins de 22 octets , c'est facile, mes décomptes sont peut-être faux, merci de me le signaler .

Ah oui. Excellent. Jolie la boucle avec le X>0?. Je ne me souvenais plus de l'existence de ce test
En fait, toute l'optimisation est la (et j'aurais du percute car les differrents codes de C.Ret embarquaient deja cette solution).
@C.Ret : Tu vas faire des merveilles avec ton HP71B

[C.Ret]

Je suis surpris, personne n'a envisager d'utiliser une méthode par récurrence :

D'après l'idée originale, qui nécessite de laisser actif le mode de récupération par LAST:

Code : Tout sélectionner

« 2 MOD LAST / IP DUP « MPO96 » IFT + » 'MPO96' STO

Utilisation 1968 MPO96 renvoi 6.

Sur l'idée de Gilles59 en utilisant la division comme Bernouilli92 par deux et FP :

Code : Tout sélectionner

« 2 / FP LAST IP DUP « MPO96 » IFT DUP + + » 'MPO96' STO

Utilisation 1968 MPO96 renvoi 6.


Et sur l'idée de Gege32, son pendant utilisant les entiers de type binaire :

Code : Tout sélectionner

« DUP #1b AND SWAP SR B→R DUP « R→B  bMPO96 » IFT + »  'bMPO96' STO

Utilisation en mode DEC : #1968d bMPO96 renvoi # 6d.
Utilisation # 2305843009213693953d bMPO96 renvoi # 4d.

[C.Ret]

Ce programme fonctionne sur PB-1000 pour des valeurs de N jusqu'à 2^32-1 (avec 8 itérations) :

Code : Tout sélectionner

10 INPUT N:N1=INT(N/65536):N2=N-65536*N1:N=0
20 N$=HEX$(N1):GOSUB 50
30 N$=HEX$(N2):GOSUB 50
40 PRINT N:GOTO 10
50 FOR I=1 TO 4:C$=MID$(N$,I,1)
60 IF C$="0" THEN 110
70 IF C$="F" THEN N=N+4:GOTO 110
80 IF C$="1" OR C$="2" OR C$="4" OR C$="8" THEN N=N+1:GOTO 110
90 IF C$="7" OR C$="B" OR C$="D" OR C$="E" THEN N=N+3:GOTO 110
100 N=N+2
110 NEXT: RETURN

Bonne idée, qui m'a bien inspirée ET que j'ai un peu "comprimée" ce qui donne un bout de code plus court:

MPO96 - C128D BASIC 7.0 solution.gif (36.72 Kio) Vu 8096 fois

Mais, je me suis dit, c'est bien pour les BASIC qui ont des instruction HEX$() , DEC(), etc.

Mais pour du BASIC plus primitif ?? Alors j'ai redonné un petit coup de "compresseur" :

MPO96 - C128D BASIC 2.0 solution.gif (36.92 Kio) Vu 8096 fois

[Gilles59]

@Gilles59 pourquoi pas un while au lieu d’un do? Cela permet d’éviter le not.

Il me semble que ça ne marche pas dans ce sens là...
J'avoue que je jongle de moins en moins avec la pile car en NewRPL ca ralentit (un peu) versus des variables :O...

[Schraf]

Je continue à reprendre tranquillement d'anciens MPO, c'est vraiment intéressant de lire tous ces fils de discussion (enfin là je ne vous apprends rien).

Par rapport à ce MPO, on voit que le calculateur HP-16C avec son #B semble imbattable mais est limité au nombre entré en paramètre. Je propose ici l'inverse, à savoir pouvoir entrer des nombres jusqu'à 300 chiffres et en sortie obtenir le nombre de 1 en écriture binaire.

Un nombre de 300 chiffres s'écrit sur un peu moins de 1000 bits soit la taille maximale d'une liste sur les Ti-83 Plus, Ti-84 Plus ou les Premium CE.

Voici l'idée du programme :

Code : Tout sélectionner

{0}→L₁				Initialisation de la liste qui contiendra les bits 0 ou 1
Repeat 0			
Input N				On entre les chiffres un par un en partant de la gauche
If N=-­1:Stop
augmenter({0,0},L₁→L₂		Ajouter 2 zéros revient à multiplier par 4 en binaire
augmenter(L₁,{0,0}→L₁		On s'arrange pour que l'autre liste ait la même dimension
L₁+L₂→L₁			Ajouter ces 2 listes revient à multiplier par 1 + 4 = 5
augmenter({0},L₁→L₁		On multiplie la liste par 2 soit par 2 * 5 = 10 au total
For(K,1,dim(L₁			On parcourt la liste
reste(N,2)+L₁(K→A		Calcul de la nouvelle valeur de L₁(K) qui peut être 0,1 ou 2
reste(A,2→L₁(K			Valeur finale sans retenue
If A>1				S'il y a une retenue :
Then
If K=dim(L₁			Est-on à l'extrémité de la liste ?
Then
augmenter(L₁,{1}→L₁		Ajouter un 1
Else
1+L₁(K+1→L₁(K+1			Ajouter 1 à L₁(K+1)
End
End
ent(N/2→N			Actualisation de N (divisions successives par 2 pour la décomposition en binaire)
End
Disp som(L₁			Nombre de bits à 1
End

Exemple avec 31415926535897932384626433832795 qui visiblement à 52 bits à 1...

52 bits sont à 1

piBIN.png (7.25 Kio) Vu 6354 fois

[Schraf]

Version pour les calculatrices compatibles Python.

Code : Tout sélectionner

n = int(input())
print('Bits 1 =', bin(n).count("1"))

31415926535897932384626433832795

piBIN.png (8.44 Kio) Vu 6347 fois

[C.Ret]

Ah!Ah! Je débute en Python, j'ai réussi à faire tourner ton programme sur mon HP Prime !!

MPO96 - HP Prime (Python App).png (15.03 Kio) Vu 6340 fois

Je confirme, il y a bien 52 bits à un dans ce nombre ! La ligne qui indique qu'il n'y en a que 40 provient du fait que j'avais laissé mon HP Prime en mode 32 bits. En mode 64 bits, je trouve le bon résultat

Comme c'est sur une HP, j'ai remplacé ton label " Bits 1 = " par "#B =" comme sur une HP-16C (Je vais pas réinventer des fonction qui existe déjà !!

MPO96 - HP Prime (Python App) First Step in Python.png (8.16 Kio) Vu 6340 fois

[Schraf]

C.Ret, comme j'ai eu plusieurs fois la remarque par rapport à mes vidéos consacrées à Python, je te donne l'autre façon de formater une sortie :

Code : Tout sélectionner

n = int(input())
print('#B({0})={1}'.format(n, bin(n).count("1")))