Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 17-04-2024 20:36:37

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

rPeuve d'algorithme

Une petite énigme qui est bien mathématique, quoi qu'on en pense.

La fonction suivante (made by bibi, mais je pense qu'elle doit déjà exister en cherchant bien) compte le nombre de "1" dans l'écriture binaire d'un enter 64 bits.
Du moins... c'est moi qui vous le dit big_smile

Code:

int countOnes(unsigned long number) {
    number = number - ((number>>1) & 0x7777777777777777) 
        - ((number>>2) & 0x3333333333333333) 
        - ((number>>3) & 0x1111111111111111);
    return (((number + (number >> 4)) & 0x0F0F0F0F0F0F0F0F) 
        * 0x0101010101010101 ) >> 56;
}

Votre tache : démontrer que cette fonction renvoie bien ce qu'elle est supposée faire.

Note : l'avantage de cette fonction est qu'elle est hyper optimisée, bien plus qu'une boucle sur les 64 bits du nombre : à titre d'exemple, sur la même machine (la mienne), la boucle standard mettra 30 secondes pour 100 millions de cas, et celle-ci en traitera un milliard en une demi-seconde.

  • |
  • Répondre

#0 Pub

 #2 - 18-04-2024 02:19:55

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Preuve d'alorithme

Grille de lecture pour les non-initiés :

0x… représente un nombre hexadécimal

& est l’opération logique AND, qui vaut 1 si les deux opérandes valent 1
(Et dans le cas d’entiers, c’est la même opération bit à bit)

a >> n est le décalage vers la droite de n bits de a
(autrement dit on supprime les n derniers bits de a, et on ajoute n zéros au début)

 #3 - 19-04-2024 13:51:49

LeJeu
Passionné de Prise2Tete
Enigmes résolues : 25
Messages : 74

Preuve d'algorrithme

Bonjour Scarta

Je te lis à l'instant : très joli !

Dans un première lecture on  a l'impression que le bidule compte le nombre de  1 dans chaque paquet de 4 bits

Je sais je ne montre rien... Mais je ne suis à l'instant qu'avec mon tél..

On doit pouvoir tester assez facilement sur des nombres à 8 bits : en ne gardant que 2 caractères dans tous les 0xHH de ton algo  donc respectivement 77 33 11 0F 01.

Et la j' hésite sur le 56..
Je dirais a remplacer par 7

Je te confirme /infirme ça quand je retrouve un clavier

Si  c'est bien ok, on s'intéressa à la validation de l'algo dans ce cas simplifié !

 #4 - 19-04-2024 14:14:58

LeJeu
Passionné de Prise2Tete
Enigmes résolues : 25
Messages : 74

Preuve d'algorithe

Avec un compilateur sur le web
J'ai le code ci dessous
Qui marche pour des int 8b

Et pas de shift 56...
255 donne bien 8 et 254 donne 7
On progresse doucement...

Code:

/***********************
Online C Compiler.
**********************/

#include <stdio.h>
int countOnes(unsigned long number) {
    number = number - ((number>>1) & 0x77) 
        - ((number>>2) & 0x33) 
        - ((number>>3) & 0x11);
    return (((number + (number >> 4)) & 0x0F) 
        * 0x01 ) ;
}
int main()
{
    int nb =254;
    printf("%d %d",nb,countOnes(nb));

    return 0;
}

 #5 - 20-04-2024 10:38:17

LeJeu
Passionné de Prise2Tete
Enigmes résolues : 25
Messages : 74

Preuvve d'algorithme

Le premier calcul
  number = number - ((number>>1) & 0x7777777777777777)
        - ((number>>2) & 0x3333333333333333)
        - ((number>>3) & 0x1111111111111111);

compte bien les 1  par parquet de 4 : c'est dire 4 bits, par exemple, 1111 est remplacé par son nombre de 1, ici  la valeur 4 ,  écrit donc 0100

et cela 16 fois l'un derrière l'autre

le deuxieme calcul
((number + (number >> 4)) & 0x0F0F0F0F0F0F0F0F)

va additionner les  valeurs  donnés par 4bits et les 4 suivants
par exemple 8 bits à 1111 1111
sont remplacés par le 1° calcul par 0100 0100 ( quatre quate)
et remplacés par le 2° calcul par 00001000 ( huit)

A ce stade on a donc un nombre de 8 octets, chaque octet comprenant le nombre de 1 de l'octet initial ( de 0 à 8)
"Ne reste plus" qu'a additionner ces 8 octets

C'est la fin du calcul
* 0x0101010101010101 ) >>  (64-8);
C'est à dire on multiplie et on garde les 8 bits de gauche

en effet la multiplication par (0x0101010101010101) revient à faire la somme des multiplications par (0x0100000000000000) et ((0x0001000000000000).......(0x0000000000000001)
Chaque multiplication faisant un shift de  0 ,2.... 7 octets vers la gauche
on retrouve donc la somme des 8 octets dans le premier

que l'on récupère au final par le shift de ( 64 - 8) bits vers la droite

LeJeu
Peut être faudrait il détailler davantage le mécanisme du 1° calcul

 #6 - 22-04-2024 00:47:37

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

preuve d'algoriyhme

C’est exactement ça !
Pour être plus précis il conviendrait d’expliquer pourquoi j’ai besoin de paquets de 8 plutôt que de paquets de 4: avec des paquets de 4 on arrive à un maximum de 15, or je peux monter jusqu’à 64 —> il me faut des paquets d’au moins 7 bits — et tant qu’à faire on arrondit à 8

Pour le 1er calcul :
Soit N <16, on a
N = 8a+4b+2c+d
N>>1 = 4a +2b + c
N>>2 = 2a+b
N>>3 = a
Et en faisant la soustraction de tout ça on obtient… a+b+c+d. L’étape 1 c’est pareil mais par blocs.

Cet algorithme fait du calcul parallèle sur plusieurs blocs de données mais avec des opérations atomiques, d’où son efficacité.

Variante :
N = N - ((N>>1) & 0x5555…..) —> paquets de 2
N = (N & 0x333….) + ((N>>2) & 0x3333….) —> paquets de 4
Et la suite est la même.

 #7 - 22-04-2024 00:55:00

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Preuve d'alggorithme

J’ai essayé d’autres variantes : 21 paquets de 3 qui donnent 10 de paquets de 6 et on prend les 4 premiers bits à part, celle mentionnée ci dessus, paquets de 8 directement, …
La version initiale reste celle qui donne les meilleurs performances. Pour certaines variantes ca se joue à la pico-seconde mais bon.

A noter que si on écrit un algorithme naïf, mais qu’on compile le code avec gcc -O3 pour activer les optimisations, gcc détecte le « but » de la fonction et la remplace par sa propre fonction __builtin_popcount, qui est la variante du post précédent

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
25-04-2024 Enigmes Mathématiques
17-06-2015 Enigmes Mathématiques
26-02-2014 Enigmes Mathématiques
P2T
La preuve par 16 ! par SaintPierre
25-02-2011 Enigmes Mathématiques
P2T
Preuve 2=1 par Mariiella
12-09-2011 Enigmes Mathématiques
18-02-2016 Enigmes Mathématiques
P2T
Dés 2 par Vasimolo
30-06-2012 Enigmes Mathématiques
P2T
Dans le rayon "ellipse"... par SaintPierre
15-08-2011 Enigmes Mathématiques
05-12-2011 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete