Enigme Preuve d'algorithme @ Prise2Tete

scarta · #1

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

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.

scarta · #2

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)

LeJeu · #3

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é !

LeJeu · #4

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;
}

LeJeu · #5

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

scarta · #6

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.

scarta · #7

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

Preuv d'algorithme

Code:

#0 Pub

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

pteuve d'algorithme

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

Preuve d'algorihtme

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

preuve s'algorithme

Code:

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

Preuve d'algorithm

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

Preuvve d'algorithme

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

Preuve d'lgorithme

Réponse rapide

Sujets similaires

Pied de page des forums