decomposition binaire

Version imprimable

Voir 40 message(s) de cette discussion en une page

03/02/2006, 15h37
muquet

decomposition binaire

Bonjour
J’ai un code binaire a exploiter :

je sais que
1 = element 1
2 = element 2
4 = element 3
8 = element 4
16 = element 5
32 = element 6
64 = element 7
128 = element 8
etc ...

Pour me donner une liste d'éléments, on me donne, par exemple : 67 qui est en fait 64 + 2 +1 donc en binaire :
67 = 1000011 en binaire
= 1000000 + 10 + 1 donc en fait les element 1,2 et 7

pour résume je reçois 67 et je dois en retirer : element 1,2 et 7

Comment je 1 : décompose en binaire et 2 comment je trie ?

Quelqu’un a une idée ou une autre solution ?

Merci

Re: decomposition binaire

si ça peut t'aider, j'avais fait ça, il y a longtemps, j'ai essayé de le sortir de son contexte:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 deci1:=edit1.text; Repeat Inc(index); Qo:=deci div 2; reste:=deci Mod 2; deci:=Qo; case index of 1: a:=reste; 2: b:=reste; 3: C:=reste; 4: d:=reste; 5: e:=reste; 6: f:=reste; 7: g:=reste; 8: h:=reste; end; until Qo=0; Label1.caption:=intTostr(h)+intTostr(g)+intTostr(f)+intTostr(e)+intTostr(d)+intTostr(c)+intTostr(b)+intTostr(a);
c'est sorti de son contexte, je me souviens plus parfaitement de ce que j'avais fait. c'était pour un afficheur.
pour trier, méthode du tri bulle par exemple.
je dois avoir ça en rayon si tu en as besoin...

Code:

1
2
3
4
5
6
7
8
9
function BinExo( Inb: Integer ): string;
var
   i : Integer;
begin
     Result := '';
     for i := 0 to 31 do
       if ( Inb and ( 1 shl i ) ) <> 0
         then Result := Result + IntToStr( i + 1 ) + ';';
end;

on doit pouvoir optimiser mais je te laisse le soin ;)

faut adapter si l'entier est sur 64 bits

salut.
Meme idée que TicTacToe

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function Parser(Const AValue : Integer):Variant;
Var
  i, lg : Integer;
begin
  Result := Null;
  lg := 0;
  For i := 0 To 31 Do Begin
    If ( ( AValue And ( 1 shl i) ) > 0 ) Then Begin
      If VarIsNull(Result) Then
        Result := VarArrayCreate([0,0],varInteger)
      Else
        VarArrayRedim(Result,lg);
      Result[lg] := Succ(i);
      Inc(lg);
    End;
  End;
end;
 
 
procedure TForm1.Button1Click(Sender: TObject);
Var
  v : Variant;
  i : Integer;
  s : String;
begin
  v := Parser(StrToInt(Edit1.Text));
  If VarIsNull(v) Then
    Edit2.Text := 'NULL'
  Else Begin
    s := '';
    For i := VarArrayLowBound(v,1) To VarArrayHighBound(v,1) Do
      s := s + ' , ' + IntToStr(v[i]);
    Delete(s,1,2);
    Edit2.Text := s;
  End;
end;

03/02/2006, 18h48
tourlourou

regarde pê aussi du côté de TBits en déclarant un Word et un TBit absolute ?

Bonjour

On peut faire aussi.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
Procedure testValue( AValue : Integer);
Var 
  Index, tmpI : integer;
Const 
  MaxValue = 31; // à modifier selon la valeur maxi possible
Begin
tmpI := 1; // initialisation de la varible tampon
For index := 0 to MaxValue do
  Begin
  If (AValue and tmpI) = tmpI then // exploitation de l'élément de rang Index ( attention, index commence à 0 et non 1)
  tmpI := tmpI * 2; 
  End;
end;

04/02/2006, 02h45
LadyWasky

Personellement, je ferais comme bjl ou TicTacToe :wink:

En effet, comment tester un bit en binaire ?

imaginons que tu ais un nombre en binaire :

Citation:

01000011

et que tu veuilles tester l'élément numéro 3 (qui est égal à 0)

Alors tu prends le nombre binaire, dont seul le bit n°3 est égal à 1, c'est à dire :
[quote]00000100[/quote]
On appelera celà un "masque"

si tu effectues un ET logique, bit à bit, entre c'est deux nombres binaires, tu sera sur que le nombre résultant aura tout ses bits qui ne sont pas le n°3 égaux à 0 puisque quelque soit leurs valeurs, les bits de 1000011 différent du numéro 3, seront "masqués" par les 0 de 00000100. donc tu auras :

Citation:

TonNombre and 00000100=00000X00, X restant à déterminer

Concernant la valeur de X, elle sera égale à l'élément n°3 and 1

Si cet élément n°3 vaut 1, alors X sera égal à 1, sinon il sera égal à 0. Donc dans tous les cas, le résultat que tu obtiendra sera :
- 0000000 si l'élément n°3 est égal à 0
- 00000100 (donc égal à ton masque) si l'élément n°3 vaut 1

De là tu en conclues :
- Si (TonNombre and 00000001)=00000001 alors le bit n°1 est égal à 1 sinon 0
- Si (TonNombre and 00000010)=00000010 alors le bit n°2 est égal à 1 sinon 0
- Si (TonNombre and 00000100)=00000100 alors le bit n°3 est égal à 1 sinon 0
- Si (TonNombre and 00001000)=00001000 alors le bit n°4 est égal à 1 sinon 0
- etc...

Après, pour tester les différents bits de ton nombre (en l'occurence 67), tu le testera ton nombre, successivement avec 00000001, 000000010, 00000100, etc... autrement dit 1, 2, 4, 8, 16, 32, 64, etc... en décimal.

C'est tout simplement ce que réalise le code de bjl, qui va tester

Code:

(AValue and tmpI)=tmpI

, avec tmpI successivement égal à 1, 2*1=2, 2*2=4, 2*4=8, 2*8=16, etc... (il multiplie à chaque fois tmpI par 2 pour préparer la boucle suivante).

TictacToe, quand à lui effectue le test de cette manière élégante :

Code:

( Inb and ( 1 shl i ) ) <> 0

a shl b effectue un décalage des bits du nombre a de b fois vers la gauche, ce qui signifie dans son code que le bit du nombre 1 est décalé b fois vers la gauche, en rajoutant b fois un 0 après le bit n°1.

ainsi, 111 shl 2=11100 111 shl 3=111000.

donc à partir du nombre 1 (00000001 en binaire), il obtiendra en fonction de i :
1 shl i=
i=0 --> 0000001
i=1 --> 0000010
i=2 --> 0000100
... etc...

Tu auras sans doute constaté que

Citation:

UnNombre shl 1 = UnNombre * 2

En fait shl permet d'effectuer très rapidement une multiplication par deux.
Ainsi, bjl aurais pu fortement optimiser son code en écrivant :

Code:

tmpI := tmpI shl 1;

à la place de :

Code:

tmpI := tmpI * 2;

:P

Pour la division par deux, tu as le décalage des bits par la droite avec l'opérateur shr
J'espère qu'on aura pu t'aider à la hauteur de tes espérances.

:wink:

Salut
Pour ma part je te soumets ce code qui m'avait permis de convertir un nomtre entier en suite de 1 ou 0 représentant la valeur binaire
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 function hexatobin(valeur:longword):string; var c:byte; lgbin:shortint; tempo:string; begin lgbin:=-1; tempo:=''; repeat inc(lgbin); until power(2,lgbin)>valeur; dec(lgbin); for c:=lgbin downto 0 do if valeur>=power(2,c) then begin tempo:=tempo+'1'; valeur:=valeur-trunc(power(2,c));end else tempo:=tempo+'0'; result:=tempo; end;
Le principe est simple

On commence par déterminer la "longueur" du nombre binaire en comparant l'entier à convertir aux puissances successives de 2. Dès que cette valeur < une puissance quelconque de 2, on en déduit le nombre de bits qui est égal à cette puissance. Par ex 7 qui est < 2 puissance 3 contient 3 bits (111 en binaire)

Il ne reste plus qu'à appliquer la règle suivante:
Si le nombre en question est >= 2 puissance n, alors le bit de poids n est à 1 et dans ce cas, on soutrait cette puissance de 2 au nombre à convertir et on continue jusqu'à 2 puissance 0...

Cette méthode n'est pas comparable à celle de Wascol, très "informatique"
Ce ne sont que quelques éléments de réflexion supplémentaires...
Alors si ça peut t'aider

Bonne prog

04/02/2006, 13h15
TicTacToe

Bravo Waskol pour ce cours complet sur les mnipulations de bit. :D

Effectivement, en tout cas à l'époque,

en nombre de cycle processeur, ca ne coute pas plus cher de faire un décalage de 1, qu'un décalage de X.

(mais bcp plus rapide qu'une multiplication par 2, mais là, je soupconne Delphi de faire l'optimisation lui meme et de remplacer tout multipliation par 2^x par un shl x...) -> a décompiler pour voir.

Du coup, pas besoin de masque intermédiaire qui est décalé au fur et à mesure, ca rajoute une variable inutilement, autant tester la nombre par rapport au masque calculé en temps réel.

Petite remarque, dans ces manipulations et décalage, il faut faire attention au bit de signe. qui pour un entier sur 32 bit, se situe au bit 31. Donc les décalage doivent tenir compte de cela ! sinon, les type qu'il faut prendre sont des types non signés

juste pour le fun :

Code:

1
2
3
4
5
6
7
8
9
function TesteBit(Dans: Cardinal ; QuelBit : Cardinal): Boolean;
begin                                        
 asm
  MOV  EBX, QuelBit    // met QuelBit dans EBX
  BT   EAX, EBX          // teste le bit de rang EBX dans EAX (<=> Dans) en positionnant la retenue (CF)
  SBB  EAX, EAX        // met CF dans EAX
  AND  EAX, 1            // teste si présent
  MOV  Result, AL      // renvoie le résultat
 end;

Citation:

Envoyé par tourlourou

juste pour le fun :

Code:

1
2
3
4
5
6
7
8
9
function TesteBit(Dans: Cardinal ; QuelBit : Cardinal): Boolean;
begin                                        
 asm
  MOV  EBX, QuelBit    // met QuelBit dans EBX
  BT   EAX, EBX          // teste le bit de rang EBX dans EAX (<=> Dans) en positionnant la retenue (CF)
  SBB  EAX, EAX        // met CF dans EAX
  AND  EAX, 1            // teste si présent
  MOV  Result, AL      // renvoie le résultat
 end;

:mouarf3:

Très joli !

Citation:

Envoyé par tourlourou

juste pour le fun :

Code:

1
2
3
4
5
6
7
8
9
function TesteBit(Dans: Cardinal ; QuelBit : Cardinal): Boolean;
begin                                        
 asm
  MOV  EBX, QuelBit    // met QuelBit dans EBX
  BT   EAX, EBX          // teste le bit de rang EBX dans EAX (<=> Dans) en positionnant la retenue (CF)
  SBB  EAX, EAX        // met CF dans EAX
  AND  EAX, 1            // teste si présent
  MOV  Result, AL      // renvoie le résultat
 end;

Deux lignes de moins, avec la directive register :

Code:

1
2
3
4
5
6
function TesteBit(Dans: Cardinal ; QuelBit : Cardinal): Boolean;Register;
asm
  BT   EAX, EDX          // teste le bit de rang EBX dans EAX (<=> Dans) en positionnant la retenue (CF)
  SBB  EAX, EAX        // met CF dans EAX
  AND  EAX, 1            // teste si présent
end;

05/02/2006, 10h28
tourlourou

Classe !
:bravo:
05/02/2006, 12h50
TicTacToe

on s'amuse, on s'amuse mais
je crois que vous avez fait peur à Muquet, plus de reply

:wink:

Mais si, encore une :)

Citation:

Envoyé par OutOfRange

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
function hexatobin(valeur:longword):string;
var
  c:byte;
  lgbin:shortint;
  tempo:string;
begin
  lgbin:=-1;
  tempo:='';
  repeat
    inc(lgbin);
  until power(2,lgbin)>valeur;
  dec(lgbin);
  for c:=lgbin downto 0 do
    if valeur>=power(2,c) then begin
      tempo:=tempo+'1';
      valeur:=valeur-trunc(power(2,c));end
    else tempo:=tempo+'0';
  result:=tempo;
end;

en méthode "waskol" ça donne

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
function hexatobin(valeur:longword):string;
var
 i : Integer;
 t : longword;
 HadOne : Boolean;
begin
 Result := '';
 HadOne := False;
 for i := (SizeOf(longword)*8)-1 downto 0 do
  begin
 
   if (valeur and (1 shl i)) <> 0 then
    begin
     Result := Result + '1';
     HadOne := true;
    end
   else
    begin
     if HadOne then
      Result := Result + '0';
     end;
 
  end;
 
  if Result = '' then
   Result := '0';
end;

Puisqu'on en est dans les fonctions en Pascal pur : voici plus court et plus rapide :
Code:

1 2 3 4 5 6 7 8 function hexatobin(valeur:longword):string; Begin Result:=''; Repeat Result:=Chr(48+Ord(Odd(Valeur)))+Result; Valeur := Valeur shr 1; Until Valeur=0; End;

:king:
Quand j'y pense, ce serai bien aussi de pouvoir spécifier un bit à la foi :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
function getBit(val : Integer;pos : Integer) : Boolean;
 begin
  Result := (val and (1 shl pos)) <> 0;
 end;
 
 procedure setBit(var val : Integer;pos : Integer;
                  BitVal : Boolean);
 var
  ActualVal : Boolean;
 begin
  ActualVal := getBit(val,pos);
  if(ActualVal <> BitVal) then
   begin
    val := val shr pos;
 
    if(ActualVal = True) then
     val := val -1
    else
     val := val +1;
 
    val := val shl pos;
   end;
 end;

:) ( c'est amusant tout ces décallages )

05/02/2006, 19h04
Nono40

:arrow: smyley
Ton code ne foctionne pas, il met à zéro tout les bits inférieurs à pos dans val :wink:
05/02/2006, 21h07
Henri_13

Bonsoir tout le monde,

Je me permet de rester dans ce post qui car ma question concerne aussi le binaire au sujet du code de nono, dont je suis entrain d'utiliser pour convertir un décimal entier en binaire, de quelle manière faut il procéder afin d'obtenir un résultat binaire sur 8 bits en comblant pas des 0 par exemple (10 = 00001010) au lieu de 1010 :oops:

Merci à vous :)

Codialement Henri

Citation:

Envoyé par Nono40

:arrow: smyley
Ton code ne foctionne pas, il met à zéro tout les bits inférieurs à pos dans val :wink:

Oui en effet j'avais remarqué,
il faut spécifier les bytes par ordre décroissant pour construire son nombre :?
celà dit, y as-t-il une méthode qui permet de faire "tourner" les bytes ? ( c-à-d de 10100 passer à 01001, puis à 10010 ? )
sinon on pourrai toujours passer par un longword temporaire :roll:

Citation:

Envoyé par Henri_13

sur 8 bits en comblant pas des 0 par exemple (10 = 00001010) au lieu de 1010
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 function hexatobinByte(valeur:byte):string; var i : Integer; begin Result := ''; for i := (SizeOf(byte)*8)-1 downto 0 do begin if (valeur and (1 shl i)) <> 0 then Result := Result + '1' else Result := Result + '0'; end; if Result = '' then Result := '0'; end; procedure TForm1.Button5Click(Sender: TObject); begin ShowMessage(hexatobinByte(10)); //renvoi 00001010 end;

Voir 40 message(s) de cette discussion en une page