Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
628 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  [Algo C] Question sur calcul b parité

 


 

 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Algo C] Question sur calcul b parité

n°2038041
utb diablo
.: :. 4 ever xo0
Posté le 24-11-2010 à 11:29:22  profilanswer
 

Salut les gens,
 
j'ai juste une petite question sur un algo trouvé sur le net permettant de calculer un bit de parité  http://graphics.stanford.edu/~sean [...] With64Bits
 

Code :
  1. unsigned char b;  // byte value to compute the parity of
  2. bool parity =
  3.   (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
  4. /*   http://www.anderoid.com/~seander/a [...] hacks.html
  5.                                                           abcdefgh
  6. * 0000000100000001000000010000000100000001000000010000000100000001 = 0x0101010101010101ULL  // got it
  7. ==================================================================
  8.   abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
  9. & 1000000001000000001000000001000000001000000001000000001000000001 = 0x8040201008040201ULL  // ok got it
  10. ==================================================================
  11.   a00000000b00000000c00000000d00000000e00000000f00000000g00000000h
  12. % 0000000000000000000000000000000000000000000000000000000111111111 = 0x1FF                  // huh, wtf ?!
  13. ------------------------------------------------------------------
  14.   ????????????????????????????????????????????????????????????????
  15. & 0000000000000000000000000000000000000000000000000000000000000001 = 0x01
  16. ==================================================================
  17.                                                                  X
  18. */


 
Pour l'instant j'ai "compris" la multiplication et le premier ET logique, le modulo 0x01FF par contre, je vois pas du tout comment il fonctionne.
Le dernier &1, il sert à récupérer le LSB, c'est ca ?
 
J'ai cherché sur le net comment marchait un division/modulo au niveau binaire, mais j'ai soit pas/mal compris les codes que je voyait, soit la solution est tellement simple que j'ai du passer à côté ..
 
 
Voila, si quelqu'un a des infos pour me permettre de comprendre ce modulo, ce serait sympa.
 
++


Message édité par utb diablo le 24-11-2010 à 13:52:22

---------------
Au royaume des aveugles, les borgnes sont rois xo0
mood
Publicité
Posté le 24-11-2010 à 11:29:22  profilanswer
 

n°2038064
olivthill
Posté le 24-11-2010 à 13:31:58  profilanswer
 

Citation :

Le dernier &1, il sert à récupérer le LSB, c'est ca ?

Oui.

Citation :

le modulo 0x01FF par contre, je vois pas du tout comment il fonctionne.

C'est un modulo 512, pour avoir le reste de la division par 512. A la ligne 13, ce n'est pas une multiplication, mais un modulo.
1FF est 512, et c'est une série de neuf 1. La parité d'un octet est un neuvième bit. Donc, ce n'est pas très surprenant d'utiliser 512.
 
Cela dit, je ne sais pas si cette formule marche bien. Par exemple la parité de 4 devrait être 1 et la parité de 6 devrait être 0. Or, sauf erreur, le calcul indiqué donnera 0 pour 4 et aussi 0 pour 6. Edit : ça marche bien, j'ai fait le test.
 
Une division par 2 est la même chose qu'un décalage d'un bit. Un modulo par 2 est la même chose qu'un masquage du dernier bit, autrement dit un & 0x01.
Donc, un modulo 512 est la même chose qu'un & 0xFF. Donc, on peut se demander pourquoi la formule enchaîne & 0xFF et & 0x01, au lieu de faire directement &0x01.Edit : voir le message de Un Programmeur.


Message édité par olivthill le 24-11-2010 à 13:59:23
n°2038068
Un Program​meur
Posté le 24-11-2010 à 13:55:53  profilanswer
 

olivthill, tu confonds % 0x1FF et & 0x1FF, & 0x1FF fait la meme chose que % 0x200.  %0x1FF fait la somme des chiffres de la representation en base 0x200  du nombre (comme %9 fait la somme des chiffres en base 10 de la representation du nombre) du moins tant que cette somme est inferieure a 0x1FF, donc ca fait la somme des groupes de 9 bits, et ici le bit de poids faible de chacun de ces groupes correspond a un bit de l'octet de depart.


Message édité par Un Programmeur le 24-11-2010 à 14:10:15

---------------
The truth is rarely pure and never simple (Oscar Wilde)
n°2038081
Un Program​meur
Posté le 24-11-2010 à 14:38:03  profilanswer
 

Variante qui ne necessite pas du 64 bits:

Code :
  1. x = b * 0x01010101UL;
  2. parity = (x & 0x08040201UL) % 0x1FF + (((b & 0x80402010UL) >> 4) % 0x1FF) & 1;


 
(je crois que ce que j'avais donne dans l'autre thread convient mieux a ta machine, tu peux toujours mesurer si tu veux).

Message cité 1 fois
Message édité par Un Programmeur le 24-11-2010 à 15:23:22

---------------
The truth is rarely pure and never simple (Oscar Wilde)
n°2038086
h3bus
Troll Inside
Posté le 24-11-2010 à 15:02:26  profilanswer
 

Un Programmeur a écrit :

Variante qui ne necessite pas du 64 bits:

Code :
  1. x = b * 01010101UL;
  2. parity = (b & 08040201UL) % 0x1FF + (((b & 80402010UL) >> 4) % 0x1FF) & 1;
 

(je crois que ce que j'avais donne dans l'autre thread convient mieux a ta machine, tu peux toujours mesurer si tu veux).

 

C'est x et pas b dans la deuxième ligne...
EDIT: Et des 0x, parce que en décimal ça va pas le faire....


Message édité par h3bus le 24-11-2010 à 15:03:36

---------------
sheep++
n°2038106
Un Program​meur
Posté le 24-11-2010 à 15:23:01  profilanswer
 

Fixe.  Merci.


---------------
The truth is rarely pure and never simple (Oscar Wilde)
n°2038109
h3bus
Troll Inside
Posté le 24-11-2010 à 15:31:58  profilanswer
 

Et sinon concernant le %0x1FF, une bonne démo mathématique vaut mieux qu'un long discours.

 

Le chapitre de math d'aujourd'hui est: congruences
Ce qu'il faut savoir:
si a est congru à c
et b congru à d alors

 

a*b est congru à c*d
et
a+b est congru à c+d

 

lorsque que tu multiplie ton char par 0x01010101 tu obtient:
1*char+0x100*char+0x100^2*char+0x100^3*char

 

si ton char s'écrit abcdefgh alors lors que tu fait & 0x08040201 tu obtient
h+g*2*0x100+f*4*0x100^2+e*8*0x100^3
=h+g*0x200+f*0x200^2+e*0x200^3

 

ensuite en remarquant que 0x200 est congru à 1 modulo 0x1FF tu obtient
=h+g+f+e

 

et ton lsb est ta parité

 

[:dockbchris]


Message édité par h3bus le 24-11-2010 à 15:35:36

---------------
sheep++
n°2038560
utb diablo
.: :. 4 ever xo0
Posté le 26-11-2010 à 03:43:31  profilanswer
 

Ok Un Programmeur, pour mon µC j'avais finalement adopté le code que tu donnes sur l'autre thread, il convenait mieux à mon application.
Je ferais des tests de perf vs ton nouveau code quand j'aurai accès à la bête.
 
Hm, h3bus Merci pour ces explications :) J'en apprends tout les jours avec vous :)


---------------
Au royaume des aveugles, les borgnes sont rois xo0

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  [Algo C] Question sur calcul b parité

 

Sujets relatifs
Question sur la généricité[C sur µprocesseur] Calcul de bit de parité
Débutant, problème master mind en C.[C] Parser un arbre représentatif des dossiers
calcul entre date oracle et date pc[C#] Php hors ligne ?
Calcul de compléxitésprobleme de SharpSsh avec C#
Plus de sujets relatifs à : [Algo C] Question sur calcul b parité


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR