division en binaire

Version imprimable

division en binaire

bonjour, je suis actuellement en train d'écrire une fonction permettant de faire une division de deux nombres binaires, le problème est que ma fonction fait les calculs en considérant mes mots binaires par des nombres en base 10.

le but de ma fonction est de calculer le CRC (contrôle de redondance cyclique) c'est pour cela que j'effectue la division binaire.

voici mon implémentation C actuelle :
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 int reste_division(int dividende, int diviseur) { int i; int deg_dividende; //degré du dividende int deg_diviseur; //degré du diviseur int reste; //reste de la division int div_interm; //diviseur intermédiaire, soit 0, soit le diviseur // recherche des degres des operandes deg_dividende = degre_int(dividende); deg_diviseur = degre_int(diviseur); // recherche du reste de la division div_interm = diviseur; reste = dividende >> (deg_dividende - deg_diviseur); for(i = (deg_dividende - deg_diviseur+1); i > 0; i--) { if (((reste >> (deg_diviseur-1)) & 0x0001) == 0) reste = reste ^ 0; else (reste = reste ^ diviseur); reste = reste << 1; } return reste; }

14/12/2007, 11h33
PsychoH13
Euh...
Pourquoi n'utilises-tu pas la division donnée par le C ?

À savoir les opérateurs / et %. Appliqués à des entiers il te retourne des entiers, tu peux facilement obtenir le quotient et le reste de ta division, et comme les ordinateurs ne sont capable à la base que d'utiliser des nombres binaires, la division par les opérateurs / et % est binaire aussi.

Soit une division euclidienne définie comme telle :
dividende = diviseur * quotient + reste, les opérateurs te donnent ceci :
Code:

1 2 quotient = dividende / diviseur; reste = dividende % diviseur;
Pas besoin de chercher plus loin...
14/12/2007, 11h44
diogene

PsychoH13 :

Citation:

Pourquoi n'utilises-tu pas la division donnée par le C ?...

Il ne s'agit pas dans la question du posteur de la division euclidienne.
14/12/2007, 11h50
PsychoH13

Citation:

Envoyé par diogene

PsychoH13 : Il ne s'agit pas dans la question du posteur de la division euclidienne.

Excuse-moi mais en général on parle de reste dans une division euclidienne, et puis, l'ordinateur se base pour les entiers sur des nombres binaires, alors la division "binaire" comme il dit une division euclidienne... Et il obtiendra bien ce qu'il veut...

Et vu son programme ça ressemble fortement à la division euclidienne qu'on faisait en CM2...

Bonjour

Le code suivant te permet de calculer le reste de la division d'un dividende par un diviseur. Vu ton objectif, le diviseur est codé sur 2 octets et le dividende est un tableau de n octets, où n peut être très grand (c'est pour ça qu'on fait la division binaire).

Normalement, il marche;)

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
 
#define NBOCTETS 10
 
void DivBinOctet(unsigned char octet,int diviseur,unsigned char *tail,unsigned char *rest1,unsigned char *rest2,unsigned char *head);
 
/******************************************************************************/
/* Main : division binaire                                                    */
/******************************************************************************/
int main(void) {
    int i, diviseur=1000;
    unsigned char dividende[NBOCTETS]={0};
    unsigned char head=0, rest1=0, rest2=0, tail=0;
 
    // dividende est un tableau d'entiers compris entre 0 et 255
    for (i=0;i<NBOCTETS;i++) {
        dividende[i]=128;
    }
 
    // diviseur doit etre sur deux octets (et non nul !!)
    if ( diviseur<1 || diviseur>65535 ) {
        fprintf(stderr,"Erreur : valeur du diviseur incorrecte\n");
        exit(EXIT_FAILURE);
    }
 
    for (i=0;i<NBOCTETS;i++) {
        DivBinOctet(dividende[i],diviseur,&tail,&rest1,&rest2,&head);
    }
    printf("reste : %d\n",rest1 * 256 + rest2);
 
    return 0;
}
 
/******************************************************************************/
/* Calcule de la division binaire pour un octet                               */
/******************************************************************************/
void DivBinOctet(unsigned char octet,int diviseur,unsigned char *tail,unsigned char *rest1,unsigned char *rest2,unsigned char *head) {
    int nbbits=8, r, i;
    unsigned char bit1, bit2;
 
    *tail=octet;
    do {
        bit1 = (*tail & 128) >> 7;
        *tail <<= 1;
        bit2 = (*rest2 & 128) >> 7;
        *rest2 <<= 1;
        *rest2 ^= bit1;
        bit1 = (*rest1 & 128) >> 7;
        *rest1 <<= 1;
        *rest1 ^= bit2;
        *head <<= 1;
        *head ^= bit1;
 
        r = *rest1 * 256 + *rest2;
        if ( r >= diviseur ) {
            i = r - diviseur;
            *rest1 = (unsigned char) (i / 256);
            *rest2 = (unsigned char) (i - *rest1 * 256);
        }
    } while (--nbbits);
}

14/12/2007, 12h12
memphis710

lorsque je fais le calcul avec la calculatrice windows, je ne trouve pa le résultat souhaité.

je vous donne en pièce jointe un exemple du calcul que j'effectue à la main.

teste mon prog. Si tu veux un affichage des octets sous forme binaire, utilise le bout de code suivant.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*******************************************************************************/
/* Imprime                                                                     */
/*******************************************************************************/
void Imprime(unsigned char octet) {
    char binaire[9];
    int i;
 
    binaire[8]='\0';
    i=0;
    while( i < 8 ) {
        if ( (octet >> i) & 1) {
            binaire[7-i]='1';
        } else {
            binaire[7-i]='0';
        }
        i++;
    }
 
    printf("%s",binaire);
}

14/12/2007, 12h22
PsychoH13

Citation:

Envoyé par memphis710

lorsque je fais le calcul avec la calculatrice windows, je ne trouve pa le résultat souhaité.

je vous donne en pièce jointe un exemple du calcul que j'effectue à la main.

Non mais si tu veux faire un test pour un programme en C, fais le test en C, pas avec un autre outil...

Citation:

Envoyé par corentin59

teste mon prog. Si tu veux un affichage des octets sous forme binaire, utilise le bout de code suivant.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*******************************************************************************/
/* Imprime                                                                     */
/*******************************************************************************/
void Imprime(unsigned char octet) {
    char binaire[9];
    int i;
 
    binaire[8]='\0';
    i=0;
    while( i < 8 ) {
        if ( (octet >> i) & 1) {
            binaire[7-i]='1';
        } else {
            binaire[7-i]='0';
        }
        i++;
    }
 
    printf("%s",binaire);
}

Tu peux simplifier ça... :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*******************************************************************************/
/* Imprime                                                                     */
/*******************************************************************************/
void Imprime(unsigned char octet) {
    char binaire[9];
    int i;
 
    binaire[8]='\0';
    i=0;
    while( i < 8 ) {
        binaire[7-i]='0' + ((octet >> i) & 1);
        i++;
    }
 
    printf("%s",binaire);
}