Opérations bit à bit

Version imprimable

10/10/2006, 11h44
flo_k

Opérations bit à bit

Bonjour,
je ne savais pas ou mettre ca, j'ai un petit problème mathématique, voici une petite équation :

x = 1111 & (1000100011100110111001001110001 >> 8);
x = 1111 & (10001000111001101110010);
x = 10;

Ok, voila maintenant en connaissant x, je voudrais retrouver 8 que j'appelle y plus bas :

10 = 1111 & (1000100011100110111001001110001 >> y);

Quelles sont les étapes pour retrouver y = 8 ?

Merci de votre aide.
10/10/2006, 13h10
jc-miranda
Deja, je ne comprends pas comment tu passes de :
Code:

1 2 10 = 1111 & (1000100011100110111001001110001 >> y);
a :
Code:

1 2 10 & 1111 = 10001000111001101110010 >> y;
sachant que :
considerons a=0, b=1, c=0,
a = b & c est vrai, mais a & c = b est faux.

Et qu'en plus tu as shifte la valeur 1000100011100110111001001110001 de 8 mais maintenu le shift dans l'equation. :aie:

Je ne comprends pas bien la logique de tout ca, je l'avoue. :-?
10/10/2006, 14h56
flo_k

effectivement j'avais déja fait ces erreurs,
j'ai édité mon premier post,
reste toujours que je n'arrive pas a retrouver la valeur 8 pour mon y
10/10/2006, 15h43
Jean-Marc.Bourguet

Il y a plusieurs solutions possibles. Je ne vois guère que d'essayer toutes les possibilités et éliminer celles qui ne vont pas.
10/10/2006, 15h45
®om

Citation:

Envoyé par Jean-Marc.Bourguet

Il y a plusieurs solutions possibles. Je ne vois guère que d'essayer toutes les possibilités et éliminer celles qui ne vont pas.

Je dirais ça aussi, en plus il n'y en a pas tant que ça, il n'y a que 32 possibilités maxi (sur un int)...

Bonjour,

il n'est pas possible de trouver la solution sans passer par la méthode tu "trial and error", car l'opération de shift n'est pas réversible (elle engendre une perte d'information).

Théoriquement, il y a trois réponses valables pour l'opération : y = 8 ou 25 ou 29. (la dernière réponse (29) est sujette à caution, si il y a injection de bits à zéro sur la gauche durant le décalage, cela fonctionne).
Code:

1 2 3 4 5 6 7 8 9 10 x = 1111 & (1000100011100110111001001110001 >> 25); x = 1111 & (100010); x = 10; -------------------- x = 1111 & (1000100011100110111001001110001 >> 29); x = 1111 & (10); // ok si injection de 0 sur la gauche lors du shift à droite x = 10;
Pour retrouver au moins la première réponse il faut partir du nombre à décaler et à chaque décalage regarder si les 4 bits à droite valent '0010'. En gros il suffit juste de trouver le pattern '0010' (soit 2 en décimal) dans le nombre à décaler.

soit : x = z & (w >> y)

x := 0; // résultat
z := 15; // 1111b (constante)
w := 1148416625; // chiffre à décaler
y := -1; // compteur décalage

FAIRE
y := y + 1;
x := z & (w >> y);
TANTQUE x != 2

en C :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int main (void) { int z = 15; int w = 1148416625; int y = -1; int x = 0; do{ y ++; x = z & (w >> y); }while (x != 2); printf ("resultat : %i", y); return 0; }
resultat : 8

J'espère que ca t'aidera un petit peu.

10/10/2006, 17h08
flo_k

Citation:

Envoyé par Neitsa

Pour retrouver au moins la première réponse il faut partir du nombre à décaler et à chaque décalage regarder si les 4 bits à droite valent '0010'. En gros il suffit juste de trouver le pattern '0010' (soit 2 en décimal) dans le nombre à décaler.

Ici tu prend 0010 car tu connais la valeur :
10001000111001101110010
qui est justement la valeur que l'on souhaite retrouver en partant de la :

10 = 1111 & (1000100011100110111001001110001 >> y);

C'est bien ca ?
en faite j'aimerai faire comme si je ne connais pas le décalage a l'origine.

Merci pour vos réponses
11/10/2006, 11h32
ielbenna

Citation:

Ici tu prend 0010 car tu connais la valeur :
10001000111001101110010
qui est justement la valeur que l'on souhaite retrouver en partant de la :

10 = 1111 & (1000100011100110111001001110001 >> y);

non c'est valable si on connais pas "y" car tu doit chercher la premiere occurence où on a 1111 & 0010 = 10
autrement dit on veux trouver ça:

************0010*****
& 0000000000001111
----------------------------
= 0000000000000010

"y" sera le nombre des (*) à droite de 0010
27/10/2006, 17h04
flo_k

Je remonte mon sujet,
j'ai une autre question :

Voici une première équation :

x |= (a & b) << c; (1)

Je cherche a retrouver a et je n'arrive pas du tout,
je cherche depuis un bail, on m'a donné une solution :

a |= b & (x >> c); (2)

mais aucune idée de comment en arriver la et si elle est exacte.

Merci pour votre aide.
27/10/2006, 17h11
®om

Citation:

x |= (a & b) << c; (1)

Je cherche a retrouver a et je n'arrive pas du tout

C'est normal, ça n'est pas possible...

Ta formule est équivalente à:
x = x | ((a & b) << c)
ce qui est, en changeant de variable:
X = X | Y
avec Y = ((a & b) << c)

Or, le | (ou) n'est pas bijective, et donc il n'y a pas de fonction inverse, donc tu ne peux pas retrouver Y... Tout ce que tu peux dire, c'est que Y est plus petit ou égal à X (car seuls les bits à 1 dans X peuvent être à 1 dans Y)...
27/10/2006, 23h55
flo_k

en faite je pose cette question suite a un défi de programmation :

ici

en haut le problème
en bas la solution

Celui qui a resolver ce défi, a en quelque sorte trouver la fonction inverse;
mais impossible malgrès son code, pour moi, de retrouver les étapes qui lui ont permit d'y arriver.

Vous avez noté

Citation:

x = 1111 & (1000100011100110111001001110001 >> 8);
x = 1111 & (10001000111001101110010);
x = 10;

1000100011100110111001001110001 >> 8 = 10001000111001101110010 OK!
mais
1111 & 10001000111001101110010 = 0010 = 2 et non 10 ???

maintenant trouver y connaissant n afin de satisfaire
n = 1111 & (1000100011100110111001001110001 >> y)
peut se faire comme suit
1- exprimer n sur 4 digits en base 2 ( 4 car masque '1111' est de 4 digits)
2- cette valeur sera du type 'abcd' avec a=0 ou 1, b=0 ou 1 ...
3- chercher la / les séquences 'abcd' dans '1000100011100110111001001110001'
4- chaque fois qu'elle est détectée, on a une solution y= décalage depuis la droite entre la fin de la séquence 'abcd' et le fin de '10001...'
Dans votre cas:
Pour chercher "2" (et non 10 ) codé dur 4 bits, il faut chercher le substring
"0010" dans le string initial
un code du type
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 const s1 = '1000100011100110111001001110001'; const s2 = '0010'; var i, j,n : integer; s : array[1..length(s1)] of integer; procedure solution; begin n:=0; for i:=1 to length(s1)-length(s2)+1 do if copy(s1,i,length(s2))=s2 then begin inc(n); s[n]:=length(s1)-length(s2)-i+1; end; end;
donne dans ce cas les 2 possibilitées 8 et 25
qui sont repérées comme suit
1000100011100110111001001110001

28/10/2006, 11h26
®om

Oui OK alors c'est pas une fonction inverse (ça n'est pas une fonction, vu qu'il ya 2 antécédents). On ne peut pas répondre "c'est ça" mais "c'est ça ou ça"...
28/10/2006, 15h36
flo_k

merci j.p.mignot, c'est plus clair,
pour le 10 c'était du binaire 0010 qui vaut bien 2 en décimal

®om, pourrait tu m'expliquer ou quelqu'un d'autre si tu en as le temps bien sur, dans les grandes lignes, comment, dans le lien donné dans mon message précédent, le programmeur a réussit a créer ce "code inverse" (on va appeller ca comme ca) pour resolver le "défi"