Opérations bit à bit

**flo_k** · 10/10/2006, 11h44

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.

**jc-miranda** · 10/10/2006, 13h10

Deja, je ne comprends pas comment tu passes de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

Je ne comprends pas bien la logique de tout ca, je l'avoue. :-?

**flo_k** · 10/10/2006, 14h56

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

**Jean-Marc.Bourguet** · 10/10/2006, 15h43

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.

**®om** · 10/10/2006, 15h45

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)...

**Neitsa** · 10/10/2006, 15h56

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**flo_k** · 10/10/2006, 17h08

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

**ielbenna** · 11/10/2006, 11h32

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

**flo_k** · 27/10/2006, 17h04

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.

**®om** · 27/10/2006, 17h11

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)...

**flo_k** · 27/10/2006, 23h55

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.

**j.p.mignot** · 28/10/2006, 08h01

Vous avez noté

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**®om** · 28/10/2006, 11h26

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"...

**flo_k** · 28/10/2006, 15h36

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"

Opérations bit à bit

Algorithmes et structures de données

Discussions similaires

Partager

Partager