Question sur les décalages de bits...
cs_jb60
Messages postés
55
Date d'inscription
mardi 16 septembre 2003
Statut
Membre
Dernière intervention
4 août 2008
-
9 sept. 2004 à 20:15
racpp Messages postés 1909 Date d'inscription vendredi 18 juin 2004 Statut Modérateur Dernière intervention 14 novembre 2014 - 10 sept. 2004 à 16:07
racpp Messages postés 1909 Date d'inscription vendredi 18 juin 2004 Statut Modérateur Dernière intervention 14 novembre 2014 - 10 sept. 2004 à 16:07
62 réponses
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
22 août 2010
14
9 sept. 2004 à 23:37
9 sept. 2004 à 23:37
oui, c'est 1b
1 en binaire c'est que des zéros, sauf un 1 en poids faible, y rien a conprendre.
Modulo 2 en base 2, c'est comme modulo 10 en base 10, tu prends le 'digit de droite' en gros.
(Note que dans l'exemple que j'ai donné au début, le nombre s'écrit a l'envers: le PF est a droite).
1 en binaire c'est que des zéros, sauf un 1 en poids faible, y rien a conprendre.
Modulo 2 en base 2, c'est comme modulo 10 en base 10, tu prends le 'digit de droite' en gros.
(Note que dans l'exemple que j'ai donné au début, le nombre s'écrit a l'envers: le PF est a droite).
DeAtHCrAsH
Messages postés
2670
Date d'inscription
vendredi 25 janvier 2002
Statut
Membre
Dernière intervention
6 février 2013
9 sept. 2004 à 23:41
9 sept. 2004 à 23:41
vecchio56> J'crois bien que tu n'y a encore moins compris que moi ou alors t'es un étourdi parceque "i >> 2 &1" ca fait aussi 1b!
T'es sure d'avoir bien compris la chose ?
Parceque t'es explications sont confuses et c'est peut etre aussi confus dans ta tete :/
Shell
T'es sure d'avoir bien compris la chose ?
Parceque t'es explications sont confuses et c'est peut etre aussi confus dans ta tete :/
Shell
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
22 août 2010
14
9 sept. 2004 à 23:46
9 sept. 2004 à 23:46
Je ne vois pas ce qu'il y a de confus, a part que j'avais pas vu qu'on décalait de 2 c'est tout
int i = a + 2 * b + 4 * c; bca en base 2
i & 1 donne a
(i >> 1) & 1 donne b
(i >> 2) & 1 donne c
int i = a + 2 * b + 4 * c; bca en base 2
i & 1 donne a
(i >> 1) & 1 donne b
(i >> 2) & 1 donne c
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
9 sept. 2004 à 23:57
9 sept. 2004 à 23:57
vecchio, le bit PF (le vrai) n'a rien a voir avec le fait qu'un nombre soit pair ou impair, il indique s'il y a un nombre pair de bits positionnes dans la derniere valeur manipulee.
ciao...
BruNews, Admin CS, MVP VC++
ciao...
BruNews, Admin CS, MVP VC++
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
22 août 2010
14
9 sept. 2004 à 23:59
9 sept. 2004 à 23:59
Je n'ai jamais parlé de parité
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
10 sept. 2004 à 00:10
10 sept. 2004 à 00:10
c'etait juste pour preciser vu que tu as parle plus haut du 'bit de PF'.
ciao...
BruNews, Admin CS, MVP VC++
ciao...
BruNews, Admin CS, MVP VC++
DeAtHCrAsH
Messages postés
2670
Date d'inscription
vendredi 25 janvier 2002
Statut
Membre
Dernière intervention
6 février 2013
10 sept. 2004 à 00:18
10 sept. 2004 à 00:18
vecchio56> t'es un prof du marché au puce ma parole. T'embrouilles plus qu'autre chose mais merci quand meme d'avoir essayé.
Bon je pense avoir compris le systeme.
Voici une explication simple a ce calcul tout "bete":
Les opérateurs ">>" et "&" sont de meme priorité.
La lecture se fait donc de gauche vers la droite sans calcul intermediaire.
L'opérateur ">>" permet de décaler des bits vers la droite.L'opérateur "&" retourne 1 si les deux bits de même poids sont à 1 (ex : 3 & 5 1 car 011 & 101 1)
Soit dans notre calcul i = i >> 2 & 1 avec i=4 on a :
1) 4 = 100b
2) On applique le décalage et on obtient 001b soit 1 en décimal.
3) On compare les bits de meme poids entre 001b et 001b (qui correspond a notre 1 dans "& 1").
4) On obtient ainsi 001b.
CONCLUSION: i=1 ou i=001b et 32 post sur le forum pour comprendre le principe de la chose.! Ouf!
Shell
Bon je pense avoir compris le systeme.
Voici une explication simple a ce calcul tout "bete":
Les opérateurs ">>" et "&" sont de meme priorité.
La lecture se fait donc de gauche vers la droite sans calcul intermediaire.
L'opérateur ">>" permet de décaler des bits vers la droite.L'opérateur "&" retourne 1 si les deux bits de même poids sont à 1 (ex : 3 & 5 1 car 011 & 101 1)
Soit dans notre calcul i = i >> 2 & 1 avec i=4 on a :
1) 4 = 100b
2) On applique le décalage et on obtient 001b soit 1 en décimal.
3) On compare les bits de meme poids entre 001b et 001b (qui correspond a notre 1 dans "& 1").
4) On obtient ainsi 001b.
CONCLUSION: i=1 ou i=001b et 32 post sur le forum pour comprendre le principe de la chose.! Ouf!
Shell
cs_eRoZion
Messages postés
241
Date d'inscription
vendredi 23 mai 2003
Statut
Membre
Dernière intervention
8 octobre 2007
1
10 sept. 2004 à 00:23
10 sept. 2004 à 00:23
Moi je crois que vecchio a très bien compris.
Je comprend pas ce qui vous gène ?!
eRoZion
Je comprend pas ce qui vous gène ?!
eRoZion
DeAtHCrAsH
Messages postés
2670
Date d'inscription
vendredi 25 janvier 2002
Statut
Membre
Dernière intervention
6 février 2013
10 sept. 2004 à 00:39
10 sept. 2004 à 00:39
Au fait dans quel genre d'application on peut etre ammené a utiliser le décalage de bits et plus générallement travailler en binaire sur des bits ?
Shell
Shell
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
10 sept. 2004 à 00:53
10 sept. 2004 à 00:53
exemple tout bete pour les dates par exemple.
Si on 'pack' une date dans un DWORD:
en simili hexa: 0xAAAAMMYY
alors on peut se servir illico des '==', '>=' etc, tres performant pour ecrire un agenda.
SYSTEMTIME st;
DWORD d; // une date
d = st.wYear;
d <<= 8;
d |= (DWORD) st.wMonth;
d <<= 8;
d |= (DWORD) st.wDay;
ciao...
BruNews, Admin CS, MVP VC++
Si on 'pack' une date dans un DWORD:
en simili hexa: 0xAAAAMMYY
alors on peut se servir illico des '==', '>=' etc, tres performant pour ecrire un agenda.
SYSTEMTIME st;
DWORD d; // une date
d = st.wYear;
d <<= 8;
d |= (DWORD) st.wMonth;
d <<= 8;
d |= (DWORD) st.wDay;
ciao...
BruNews, Admin CS, MVP VC++
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
10 sept. 2004 à 01:12
10 sept. 2004 à 01:12
DeAtHCrAsH > j'avais pas fais gaffe a la priorite de >> (je lisais *p >> (i & 1) )
NitRic
Messages postés
402
Date d'inscription
mardi 1 mai 2001
Statut
Membre
Dernière intervention
15 août 2011
10 sept. 2004 à 01:39
10 sept. 2004 à 01:39
Si ca peut vous aidez:
-- Shifting bits --
http://www.harpercollege.edu/bus-ss/cis/166/mmckenzi/lect19/l19l.htm
avec de jolie images en plus :}
~(.:: NitRic ::.)~
-- Shifting bits --
http://www.harpercollege.edu/bus-ss/cis/166/mmckenzi/lect19/l19l.htm
avec de jolie images en plus :}
~(.:: NitRic ::.)~
cs_eRoZion
Messages postés
241
Date d'inscription
vendredi 23 mai 2003
Statut
Membre
Dernière intervention
8 octobre 2007
1
10 sept. 2004 à 02:06
10 sept. 2004 à 02:06
DeAtHCrAsH > "L'opérateur "&" retourne 1 si les deux bits de même poids sont à 1"
C'est faux, retourne 1 si le bit de poids faible est allumé.
DeAtHCrAsH > "Au fait dans quel genre d'application on peut etre ammené a utiliser le décalage de bits et plus générallement travailler en binaire sur des bits ?"
Un cas très bête est celui d'un soft qui doit stoqué un état qui ne peut être que A ou B (genre ampoule allumée, ampoule éteinte, pixel allumé, pixel éteint), et bien tu peux stoquer cet état sur 1 seul bit au lieu de 32 si tu utilise un int normal.
BruNews > "vecchio, le bit PF (le vrai) n'a rien a voir avec le fait qu'un nombre soit pair ou impair, il indique s'il y a un nombre pair de bits positionnes dans la derniere valeur manipulee."
Certainement que tu dois avoir raison dans un cas particulier, mais en ce qui concerne le fait que le bit de poid fort indique la parité dans un stoquage mémoire, et bien je ne pense pas ma tromper en disant que c'est vrai pour un 'signed', mais pas pour un 'unsigned', ce qui explique qu'un 'signed' ne puisse monter que jusqu'à ((2^31)-1) en positif, alors qu'un 'unsigned' peut grimper jusqu'à ((2^32)-1) toujours en positif.
En revance, tous deux possèdent 2^32 états distincts.
NB: Dans un 'signed', si le bit lourd est allumé, alors le chiffre est négatif et est calculé en faisant la somme des bits éteints !!! et non pas allumés.
Les autres >
Bon, ce truc faut faire attention sur quelle machine on s'en sert, l'exemple donné par vecchio tourne en lowendian, soit le bit de poids faible à droite.
Pour une utilisation sur mac (bigendian), faut juste remplacé l'opérateur '>>' par '<<'.
Exemple sur un chiffre à 8 bits appelé 'Chiffre' (exemple lowendian) :
76543210 /*position */
HGFEDCBA /* bits */
">>" fait péter le bit de droite (position 0) et décale les autres d'un cran vers la droite (leur position est diminuée de 1). Bit[1] devient donc Bit[0], etc...
"&1" teste le bit en position 0 (le plus à droite), le résultat vaut 0 si le bit est eteint (0) et 1 s'il est allumé (1), soit la valeur du bit (en position 0).
On applique la formule (*p >> i & 1) ou *p pointe sur 'Chiffre' :
***On commence avec i=0
_Chiffre >> i =
76543210 /*position */
HGFEDCBA /* bits */
_Resultat&1 = A
***On continu avec i=1
_Chiffre >> i =
6543210 /*position */
HGFEDCB /* bits */
_Resultat&1 = B
***On continu avec i=2
_Chiffre >> i =
543210 /*position */
HGFEDC /* bits */
_Resultat&1 = C
Et ainsi de suite, sur pc, vous avez la valeur binaire de 'Chiffre' qui s'affiche de gauche à droite dans l'ordre inverse du stoquage mémoire, soit sous la forme ABCDEFGH (noté que sur mac c'est directement dans le bon sens avec '<<').
Pour palier à ce problème sur pc, pour l'afficher en HGFEDCBA, soit sous sa forme mémoire:
int main()
{
float f = 3.14159f; // 32 bits
int* p = (int*)&f, i;
char b[32];
for(i = 0; i < 32; i++)
b[31-i]=((*p >> i) & 1);
for(i = 0; i < 32; i++)
printf("%d", b[i]);
return(0);
}
J'espère que ça mettra tout lemonde d'accord.
eRoZion
C'est faux, retourne 1 si le bit de poids faible est allumé.
DeAtHCrAsH > "Au fait dans quel genre d'application on peut etre ammené a utiliser le décalage de bits et plus générallement travailler en binaire sur des bits ?"
Un cas très bête est celui d'un soft qui doit stoqué un état qui ne peut être que A ou B (genre ampoule allumée, ampoule éteinte, pixel allumé, pixel éteint), et bien tu peux stoquer cet état sur 1 seul bit au lieu de 32 si tu utilise un int normal.
BruNews > "vecchio, le bit PF (le vrai) n'a rien a voir avec le fait qu'un nombre soit pair ou impair, il indique s'il y a un nombre pair de bits positionnes dans la derniere valeur manipulee."
Certainement que tu dois avoir raison dans un cas particulier, mais en ce qui concerne le fait que le bit de poid fort indique la parité dans un stoquage mémoire, et bien je ne pense pas ma tromper en disant que c'est vrai pour un 'signed', mais pas pour un 'unsigned', ce qui explique qu'un 'signed' ne puisse monter que jusqu'à ((2^31)-1) en positif, alors qu'un 'unsigned' peut grimper jusqu'à ((2^32)-1) toujours en positif.
En revance, tous deux possèdent 2^32 états distincts.
NB: Dans un 'signed', si le bit lourd est allumé, alors le chiffre est négatif et est calculé en faisant la somme des bits éteints !!! et non pas allumés.
Les autres >
Bon, ce truc faut faire attention sur quelle machine on s'en sert, l'exemple donné par vecchio tourne en lowendian, soit le bit de poids faible à droite.
Pour une utilisation sur mac (bigendian), faut juste remplacé l'opérateur '>>' par '<<'.
Exemple sur un chiffre à 8 bits appelé 'Chiffre' (exemple lowendian) :
76543210 /*position */
HGFEDCBA /* bits */
">>" fait péter le bit de droite (position 0) et décale les autres d'un cran vers la droite (leur position est diminuée de 1). Bit[1] devient donc Bit[0], etc...
"&1" teste le bit en position 0 (le plus à droite), le résultat vaut 0 si le bit est eteint (0) et 1 s'il est allumé (1), soit la valeur du bit (en position 0).
On applique la formule (*p >> i & 1) ou *p pointe sur 'Chiffre' :
***On commence avec i=0
_Chiffre >> i =
76543210 /*position */
HGFEDCBA /* bits */
_Resultat&1 = A
***On continu avec i=1
_Chiffre >> i =
6543210 /*position */
HGFEDCB /* bits */
_Resultat&1 = B
***On continu avec i=2
_Chiffre >> i =
543210 /*position */
HGFEDC /* bits */
_Resultat&1 = C
Et ainsi de suite, sur pc, vous avez la valeur binaire de 'Chiffre' qui s'affiche de gauche à droite dans l'ordre inverse du stoquage mémoire, soit sous la forme ABCDEFGH (noté que sur mac c'est directement dans le bon sens avec '<<').
Pour palier à ce problème sur pc, pour l'afficher en HGFEDCBA, soit sous sa forme mémoire:
int main()
{
float f = 3.14159f; // 32 bits
int* p = (int*)&f, i;
char b[32];
for(i = 0; i < 32; i++)
b[31-i]=((*p >> i) & 1);
for(i = 0; i < 32; i++)
printf("%d", b[i]);
return(0);
}
J'espère que ça mettra tout lemonde d'accord.
eRoZion
cs_eRoZion
Messages postés
241
Date d'inscription
vendredi 23 mai 2003
Statut
Membre
Dernière intervention
8 octobre 2007
1
10 sept. 2004 à 02:09
10 sept. 2004 à 02:09
Correction :
"En revance, tous deux possèdent 2^32 états distincts.
NB: Dans un 'signed', si le bit lourd est allumé, alors le chiffre est négatif et est calculé en faisant la somme DES PUISSANCES DE DEUX des bits éteints !!! et non pas allumés."
eRoZion
"En revance, tous deux possèdent 2^32 états distincts.
NB: Dans un 'signed', si le bit lourd est allumé, alors le chiffre est négatif et est calculé en faisant la somme DES PUISSANCES DE DEUX des bits éteints !!! et non pas allumés."
eRoZion
racpp
Messages postés
1909
Date d'inscription
vendredi 18 juin 2004
Statut
Modérateur
Dernière intervention
14 novembre 2014
17
10 sept. 2004 à 02:17
10 sept. 2004 à 02:17
Salut,
On utilise aussi le décalage pour multiplier ou diviser des entiers par 2, 4, 8, 16 etc. Chaque décalage vers la gauche est une multiplication par 2 et vers la droite une division. Au niveau du microprocesseur, une instruction de décalage est beacoup plus rapide qu'une multiplication. Il existe une autre variante du décalage, c'est la rotation. Le bit qui sort n'est pas perdu. Il rentre rentre dans le nombre de l'autre côté. La rotation est très utilisée dans les systèmes de cryptage de données. Il n'existe aucun opérateur pour la rotation en Visual C++. Je ne sais pas si c'est pareil pour les autres compilateurs.
On utilise aussi le décalage pour multiplier ou diviser des entiers par 2, 4, 8, 16 etc. Chaque décalage vers la gauche est une multiplication par 2 et vers la droite une division. Au niveau du microprocesseur, une instruction de décalage est beacoup plus rapide qu'une multiplication. Il existe une autre variante du décalage, c'est la rotation. Le bit qui sort n'est pas perdu. Il rentre rentre dans le nombre de l'autre côté. La rotation est très utilisée dans les systèmes de cryptage de données. Il n'existe aucun opérateur pour la rotation en Visual C++. Je ne sais pas si c'est pareil pour les autres compilateurs.
cs_eRoZion
Messages postés
241
Date d'inscription
vendredi 23 mai 2003
Statut
Membre
Dernière intervention
8 octobre 2007
1
10 sept. 2004 à 02:21
10 sept. 2004 à 02:21
En lowendian :
'<< 1' -> '*2'
'>> 1' -> '/2'
'& 1' -> '%2'
Et non, que je sache, il n'existe pas d'instruction de rotation en C/C++, tous compilateurs confondus.
eRoZion
'<< 1' -> '*2'
'>> 1' -> '/2'
'& 1' -> '%2'
Et non, que je sache, il n'existe pas d'instruction de rotation en C/C++, tous compilateurs confondus.
eRoZion
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
10 sept. 2004 à 02:47
10 sept. 2004 à 02:47
racpp > les decalages sont pas plus rapide qu'une multiplication ou une division, ton compilo les transforme en decalage
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
10 sept. 2004 à 02:49
10 sept. 2004 à 02:49
eRoZion > pour rester endianess on peut toujours s'en tenir a / et * ? (il me semble que ca avais deja ete dit)
racpp
Messages postés
1909
Date d'inscription
vendredi 18 juin 2004
Statut
Modérateur
Dernière intervention
14 novembre 2014
17
10 sept. 2004 à 03:18
10 sept. 2004 à 03:18
djl > La multiplication ou division par décalage n'est valable que pour les multiples de 2 (par 2, 4, 8 etc). On ne peut pas utiliser le décalage pour multiplier par 3 exemple. Le microprocesseur, par défaur, utilise les instructions du genre MUL ou DIV qui nécessitent beaucoup de cycles d'horloge. J'ai appris cela en programmant en assembleur pour des applications optimisées en vitesse. On nous conseillait toujours de choisir le décalage quand il s'agit d'une multiplication ou division par un multiple de 2.
racpp
Messages postés
1909
Date d'inscription
vendredi 18 juin 2004
Statut
Modérateur
Dernière intervention
14 novembre 2014
17
10 sept. 2004 à 03:59
10 sept. 2004 à 03:59
djl > Tu as raison, le compilateur transforme les multiplications ou division par 2, 4, etc par des décalages. Je viens de faire des tests en examinant le code assemleur engendré. C'est très intelligent de sa part. Il a mis SHL pour une multiplication par 2 et IMUL pour une multiplication par 3. Il est conscient de la supériorité en vitesse de SHL sur MUL dans le cas des multiplications par 2, 4 etc...
