Discussion :

[philippppe]

Bonjour!
Je suis en train d'apprendre le C, et voici une erreur de programmation de ma part que je ne comprends pas.
Mon but est de transformer les caractères ascii en binaire. Ma fonction marche plutôt bien quand je lui donne un seul caractère à transformer.
par contre, si je lui donne deux lettres ou plus elle plante et fait quitter le programme.
D’après mes tests, il semble que ce soit strcat() qui pose problème, mais pourquoi?
Ensuite, n'hésitez pas à me donner votre avis sur l'aspect général de ce bout de code. je me doute qu'il doit y avoir plus simple pour transformer un string en binaire, mais je n'ai aucun recul.

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
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
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
 
 
void IntToBin(int n, char *Bin)
{
  // divise par 2 le quotient jusqu'a le mettre a zero
  // on recupere tout les reste et on les mets bout a bout dans un string
 int entier=0;
 char convS[2];
 
 while(n/2!=0){
    // itoa converti un int en string. strcat le demande
    strcat(Bin,itoa(n%2,convS,10));
 
    n=n/2;
    if(n/2==0){
      strcat(Bin,itoa(n%2,convS,10));
      n=-1;
      }
    }
 
// retourne le resultat qui est noté a l'envers par la partie precedente de la fonction
  char retourne [(strlen(Bin))];
  int x = strlen(Bin)-1 ;
 
    for(int i =0; i<(int)strlen(Bin);i++, x--){
    retourne[x]=Bin[i];
    }
  memcpy(Bin, retourne, strlen(Bin));
}
 
 
 
int main (int argc, char* argv[]){
char binaire;
char caractere[50];
errno = 0;
 
printf(" Caracteres?\n");
fgets(caractere, 50, stdin);
 
int x =0;
while(x<(int)strlen(caractere)-1){
 
IntToBin(caractere[x],&binaire);
x=x+1;
}
 
system("PAUSE");  /* Pour la console Windows. */
return 0;
}

[dalfab]

Bonjour,

Pour convertir en texte binaire, il existe une fonction. A première vue tu la connais, elle s'appelle itoa(), mais elle ne fait pas partie de la bibliothèque standard. Donc on pourrait écrire:

Code :

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

1
2
3
4
void IntToBin(int n, char *Bin)
{
  itoa(n, Bin, 2 );
}

Mais si tu veux écrire un code qui n'utilise que les fonctions standards il faudra t'en passer.

Des erreurs de ton code:
- ligne 17: tu utilise strcat(), mais ça concatène à une chaine. Au premier appel ce que désigne Bin est aléatoire, tu dois rien y concaténer.
- ligne 27: strlen() retourne la longueur de la chaine sans le terminateur. Il faut donc ajouter 1 pour réserver aussi le terminateur \0.
- ligne 28: là il ne faut pas le -1.
- ligne 39: tu prévois un unique caractère pour recevoir en réponse à ton appel toute une chaine, ça ça provoquera un plantage. un caractère en binaire pourra donner jusqu'à 9 char.
- ligne 47, pas de -1

[foetus]

Je n'arrive pas à voir dans ton code mais je pense qu'il est foireux

La concaténation en C n'est pas celle à laquelle tu penses.
Toutes les fonctions de la librairie standard ne font pas d'allocations et s'appuient soit sur 1 taille soit sur le caractère sentinelle '\0'.

Documentation cplusplus.com de strcat en anglais .
La destination doit être suffisamment large pour y mettre destination + source + '\0'. Il n'y a pas d'allocation dynamique pour l'agrandir.
Et il faut que la destination et la source soient des chaînes de caractères C (avec le caractère sentinelle '\0')

Il faut passer par 1 log binaire pour avoir le nombre de bits d'1 nombre

Documentation cplusplus.com de itoa en anglais .
Documentation cplusplus.com de sprintf anglais : c'est la fonction à utiliser que @dalfab n'a pas mentionnée.

[Sve@r]

Bonjour

Ma fonction marche plutôt bien quand je lui donne un seul caractère à transformer.
par contre, si je lui donne deux lettres ou plus elle plante et fait quitter le programme.
D’après mes tests, il semble que ce soit strcat() qui pose problème, mais pourquoi?

Ta fonction ne marche pas du tout (même si elle "semble" fonctionner pour un caractère). En effet, ta fonction IntToBin() (un consensus assez généralisé voudrait qu'on la nomme plutôt "int2bin" mais c'est du détail) reçoit en paramètre un char *bin, donc l'adresse d'une zone à priori censée être assez large puisque la fonction y fait du strcat() à répétition (la fonction est obligée d'avoir confiance dans la zone reçue car de toute façon elle ne peut pas déterminer sa taille). Or tu lui passes l'adresse de char Binaire donc l'adresse d'une variable de taille "un char". Donc quoi que tu fasses, ta fonction n'a pas le droit de mettre plus d'un caractère dans cette zone.

Partant de là, le code tombe en UB (Undefined Behavior), état dans lequel il peut se passer n'importe quoi y compris un semblant de bon fonctionnement. En effet, la programmation en C n'admet aucune erreur car pour aller le plus vite possible il ne fait aucune vérification sur la logique des instructions.

Je n'arrive pas à voir dans ton code

Manque de sommeil (à 1h51 ça semble normal)

[foetus]

Manque de sommeil (à 1h51 ça semble normal)

Non c'est juste que lorsque j'ai vu son code, je me suis aperçu de sa chaîne à 1 caractère (et que @philippppe s'attendait à 1 concaténation str1 + str2) : j'en parle dans mon message.
Je n'avais pas envie de compiler () et surtout comme tu l'as dit, tu as 1 comportement indéfini (U.B.) : donc avec des points d'arrêts tu devrais voir/ confirmer le problème rapidement.
Donc voila, compilation, débogage, réflexion je n'avais trop envie

Et l'autre truc son algo. J'ai mis 1 petit temps à comprendre ce qu'il voulait faire. Et il m'a cassé le crane concaténation, reverse + recopie juste pour 1 conversion décimale en binaire.
On peut tout faire sur place sans recopie et sans surplus.
Après si tu prends l'algo des divisions par 2, je me méfierai parce qu'il ne faut pas te tromper de case à partir de laquelle tu commences
Je n'ai pas réfléchi/ posé l'algo, mais il n'y a peut-être pas de problème. Ou peut-être, qu'il faut juste faire en premier lieu 1 test si le nombre est pair ou impair (reste de la division par 2)

Mais pour 1 algo sur place, je prendrai l'algo des soustractions des puissances de 2 : clair et précis
Il faut vérifier mais voici 1 code qui donne l'idée (il n'y a pas d'allocations dynamiques par exemple) :

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
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
#include <stdio.h>
#include <stdlib.h>
 
 
size_t ilog2(size_t nb) {
    size_t log = 0;
 
    while (nb >>= 1) {
        log++;
    }
 
    return log;
}
 
 
void convert_int_to_bin(size_t nb, char* bin_str) {
    size_t tmp, power, count_array;
 
    tmp         = nb;
    power       = (1 << ilog2(nb)); // powl(2, ilog2(nb)); - math.h
    count_array = 0;
 
    while (power > 1) {
        if (tmp >= power) {
            bin_str[count_array] = '1';
            tmp -= power;
        } else {
            bin_str[count_array] = '0';
        }
 
        power /= 2;
        ++count_array;
    }
 
    bin_str[count_array] = ('0' + tmp);
    bin_str[count_array + 1] = '\0';
}
 
 
/*****************************************************************************/
/***********************************  Main  **********************************/
/*****************************************************************************/
 
int main(int argc, char** argv)
{
    char bin_str[33];
    size_t nb;
 
    for(nb=0; nb < 55; ++nb) {
        convert_int_to_bin(nb, bin_str);
 
        printf("%3lu: %s\n", nb, bin_str);
    }
 
 
    return EXIT_SUCCESS;
}

[WhiteCrow]

Si on tient à compter le nombre de bits qu'il faut pour représenter un entier classiquement il faut passer par un log entier en base 2. ilog2 est une fonction qui renvoie le rang (0=LSB) du bit le plus significatif positionné à 1 et 0 pour la valeur 0. Une implémentation en C pourrait être :

Code :

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

1
2
3
4
5
6
7
 
int ilog2(int value)
{
    int log=0;
    while ( value>>=1 ) log++;
    return log;
}

Le nombre de bits nécessaires pour représenter un entier n sera ilog2(n)+1.
Ensuite on alloue ce qu'il faut, soit la longueur en bit plus 1 caractère pour le zéro terminal, on se met à la fin et on remplit en checkant les bits du nombre.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
char *int2bin(int n)
{
	int bitlen=ilog2(n)+1;
	char *res=malloc(bitlen+1);
 
	char *cur=res+bitlen;
	*cur--=0;
	do {
		*cur-- = n&1?'1':'0';
	} while (n>>=1);
 
	return res;
}

[Sve@r]

Si on tient à compter le nombre de bits qu'il faut pour représenter un entier classiquement il faut passer par un log entier en base 2. ilog2 est une fonction qui renvoie le rang (0=LSB) du bit le plus significatif positionné à 1 et 0 pour la valeur 0

Mathématiquement oui. Maintenant, un int c'est au maximum 32 bits donc peut-être sacrifier l'exactitude (et le temps nécessaire à son calcul) au détriment d'un gaspillage minime de mémoire en utilisant un tableau taillé systématiquement à 32+1 ne serait peut-être pas une mauvaise idée.
En plus faut pas oublier que le PO est débutant et lui balancer du malloc (non testé) dans une fonction renvoyant un char*... saura-t-il seulement qu'il faut libérer la zone récupérée après l'avoir utilisée?

Autre chose: peut-être utiliser le fait que printf() et ses soeurs savent facilement écrire de l'hexa et que la traduction hexa <-> binaire est assez triviale (surtout que dans ce cas précis il n'y a que 16 cas à évaluer).

D'où la solution suivante

Code c :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define SZ_INT					(4)
#define NB_BITS					(SZ_INT * 8)
 
 
void int2bin(int n, char res[])
{
	char hex[SZ_INT*2+1];
	sprintf(hex, "%x", n);
	res[0]='\0';
	char *pt;
	for (pt=hex; *pt != '\0'; pt++) {
		switch (*pt) {
			case '0': strcat(res, pt != hex ?"0000" :"0"); break;
			case '1': strcat(res, pt != hex ?"0001" :"1"); break;
			case '2': strcat(res, pt != hex ?"0010" :"10"); break;
			case '3': strcat(res, pt != hex ?"0011" :"11"); break;
			case '4': strcat(res, pt != hex ?"0100" :"100"); break;
			case '5': strcat(res, pt != hex ?"0101" :"101"); break;
			case '6': strcat(res, pt != hex ?"0110" :"110"); break;
			case '7': strcat(res, pt != hex ?"0111" :"111"); break;
			case '8': strcat(res, "1000"); break;
			case '9': strcat(res, "1001"); break;
			case 'a': strcat(res, "1010"); break;
			case 'b': strcat(res, "1011"); break;
			case 'c': strcat(res, "1100"); break;
			case 'd': strcat(res, "1101"); break;
			case 'e': strcat(res, "1110"); break;
			case 'f': strcat(res, "1111"); break;
		}
	}
}
 
int main() {
	int n;
	char bits[NB_BITS + 1];
	for (n=0; n < 100; n++) {
		int2bin(n, bits);
		printf("n=%d, x=%s\n", n, bits);
	}
}

Et l'autre truc son algo. J'ai mis 1 petit temps à comprendre ce qu'il voulait faire. Et il m'a cassé le crane concaténation, reverse + recopie juste pour 1 conversion décimale en binaire.

Je vais t'avouer franchement que je n'ai même pas cherché à le comprendre Mais si tu parles de concaténation + reverse alors je présume qu'il a utilisé la méthode mathématique (divisions systématiques puis récupération des restes dans le sens inverse)...

[philippppe]

super! merci pour toute vos réponses très complètes. je relis tout bien, essaye de comprendre et je vous réponds

Edit:
En effet, j'ai simplement utilisé la méthode mathématique pour retrouver du binaire. Je n'avais pas vu que itoa peut convertir en binaire directement. Il est possible que mon algo de conversion en binaire soit foireux, bien que je l'ai testé un minimum, mais là n'es pas l'essentiel de vos enseignements.
Deux interrogations m'apparaissent maintenant.
- Quelles peuvent être les implications à utiliser ou non des fonctions qui ne sont pas de la bibliothèque standard? Et d'ailleurs d’où vient itoa() et comment se fait-il quelle ne soit pas standard puisque apparemment tout le monde la connait et l'utilise?
- J'ai bien compris avoir passé un pointeur vers un char au lieu d'une chaine. au risque de vous faire saigner les yeux, j'ai cru que tab[] et *tab était équivalent et réservaient le début d'un tableau de char, sans se préoccuper de la taille ultérieure. Belle faute donc, mais comment faire? S'il faut obligatoirement compter les bits, j'avoue ne jamais m'y être penché et être totalement largué par vos explications... du moins à la première lecture.
s'il faut déclarer dans le main un tableau assez grand, mon compilateur râle aussi quand je le lance. Je dois encore mal m'y prendre.

[Sve@r]

j'ai cru que tab[] et *tab était équivalent et réservaient le début d'un tableau de char, sans se préoccuper de la taille ultérieure.

Pas exactement.
Un tableau, c'est une zone mémoire pouvant contenir plusieurs éléments identiques. Elle est alors taillée pour avoir assez d'espace pour stocker ces éléments. Un pointeur c'est juste l'adresse d'une case mémoire.
Rien, absolument rien, n'interdit d'utiliser un pointeur pour pointer sur une case d'un tableau. Puisque le tableau existe, sa mémoire existe. De là, le pointeur peut ensuite parfaitement se balader dans les cases mémoires du tableau en s'incrémentant (ou en se décrémentant si on veut aller vers l'arrière). C'est ce que je fais quand j'écris char *pt; for (pt=hex; *pt != '\0'; pt++). Je traite tout le contenu du tableau de char "hex".

Toutefois dans l'autre sens, cela ne marche pas. Ce n'est pas parce que tu déclares un pointeur dans le but de lui mettre des datas que le C va te réserver de la place pour ça. C'est à toi de tout faire. D'où le code de WhiteCrow quand il écrit char *res=malloc(bitlen+1). Il demande au système de lui allouer un espace mémoire dont la première adresse sera stockée dans le pointeur "res". C'est ce qu'on fait quand on veut un espace dont la taille n'est pas connue au moment où on écrit le code mais est calculée dans le programme (allocation dynamique). Il existe une 3° méthode plus récente, les VLA (Variable Length Array, des tableaux de taillee variables) mais perso je ne l'aime pas car contrairement à malloc() qui renvoie NULL quand il ne peut pas allouer la zone (on peut donc savoir si ça a réussit ou pas), ave les VLA il est impossible de détecter si le tableau a ou n'a pas été créé avec la taille spécifiée.

En fait, pour faire simple, chaque fois que tu déclareras un pointeur style truc *pt, tu n'auras jamais le droit de taper dans *pt si tu n'as pas écrit quelque part au dessus pt=.... C'est impératif. A toi de t'arranger pour mettre ce qu'il faut après le "égal". Et si tu n'arrives pas à trouver quoi mettre, alors cela peut vouloir dire que ton pointeur n'est âs une bonne idée. La seule exception à cette règle du pt=... c'est si le pointeur est paramètre d'une fonction car on part alors du principe que le paramètre reçu est correct (et en réalité cela n'annule pas la règle, juste que ça la reporte sur l'appelant de ladite fonction).

s'il faut déclarer dans le main un tableau assez grand, mon compilateur râle aussi quand je le lance. Je dois encore mal m'y prendre.

Oui parce que la pile a beau être limitée, elle accepte quand-même des tailles assez significatives. Peut-être montrer ton nouveau code...

[foetus]

Il est possible que mon algo de conversion en binaire soit foireux, bien que je l'ai testé un minimum, mais là n'es pas l'essentiel de vos enseignements.

Ton code n'est pas foireux. Ton code comme celui de @Sve@r est trop long, trop d'actions, et trop d'appels à des fonctions standards (strcat, sprintf, memcpy, ...)

Regarde mon code (j'ai mis à jour mon message) et celui de @WhiteCrow : algo sur place en 1 seule boucle, avec que des opérations mathématiques/ logiques.

Quelles peuvent être les implications à utiliser ou non des fonctions qui ne sont pas de la bibliothèque standard? Et d'ailleurs d’où vient itoa() et comment se fait-il quelle ne soit pas standard puisque apparemment tout le monde la connait et l'utilise?

Il y a plusieurs inconvénients

• code non portable
• signature de la fonction qui peut changer d'1 implémentation à l'autre
• dépendant de l'implémentation - par exemple, la gestion des nombres négatifs.

Ensuite, je n'ai pas trouvé l'origine, mais je pense que c'est parce que la librairie standard est arrivée après plusieurs années après le premier compilateur.
Mais comme c'est 1 fonction assez importante alors les compilateurs l'ont intégrée.

j'avoue ne jamais m'y être penché et être totalement largué par vos explications... du moins à la première lecture.

Il faut maîtriser le binaire, l'hexadécimal et 1 peu les mathématiques

• Le log binaire ou base 2 est très utilisé : pour la hauteur d'1 arbre, les classes des sous-réseaux IPv4, ... Si X^a = b alors logX(b) = a
• Le décalage à droite de X (>> X) correspond à 1 division par 2^X.
• Le décalage à gauche de X (<< X) correspond à 1 multiplication par 2^X.

j'ai cru que tab[] et *tab était équivalent et réservaient le début d'un tableau de char, sans se préoccuper de la taille ultérieure

@Sve@r n'en a pas parlé , mais l'étoile permet de faire des passages de paramètres sortie ou entrée/ sortie.
Les débutants galèrent au début en C parce qu'en C, le passage de paramètres est par copie Ton gros tableau, c'est simple tu as fait 1 copie dans la pile et la pile, elle n'a pas apprécié (c'est le fameux "stack overflow" lorsqu'on code récursif )

*tab, tab peut être 1 variable (entière, flottante, ...) mais que la fonction va modifier.
La syntaxe crochet pour le passage de paramètres permet, il me semble , au compilateur de faire des vérifications de taille ou de type ... mais seulement pour l'unité de compilation en cours - donc assez limité (<- tu es débutant, je te laisse chercher et tester)

[philippppe]

Encore merci pour vos réponses, il va me falloir un peu de temps pour les comprendre et vous peut etre encore vous posez quelques questions.
En voici dejà une simple:

un caractère en binaire pourra donner jusqu'à 9 char.

J'avais mis 2 en imaginant recupérer des 0 et des 1. donc un seul caracteres, plus un de securité au pif (désolé c'est très mal je sais ). Pourquoi 9 char? ceci serait un exemple de 9 char? 100100100

[Sve@r]

Pourquoi 9 char? ceci serait un exemple de 9 char? 100100100

On parle d'une "représentation binaire". Cette représentation s'intègre donc dans une string. Or une string doit contenir un espace de plus que le nombre de caractères "significatifs" pour pouvoir y stocker le '\0'. C'est pour ça que dans mon code (trop long, avec trop d'actions ) j'ai définit mes strings en mettant "+1" => pour que les autres lecteurs voient que je n'ai pas oublié le '\0'.

J'avais mis 2 en imaginant recupérer des 0 et des 1. donc un seul caracteres

Tu as confondu "nombres stoclé en mémoire" et "nombre affichable". Le nombre (par exemple) 123 sera codé en binaire 0x7B (1 char) mais sera affiché '1', '2', '3' (3 char). Et si on veut le stocker dans une string C, il faudra alors un char[3+1].

[WhiteCrow]

[...]
- Quelles peuvent être les implications à utiliser ou non des fonctions qui ne sont pas de la bibliothèque standard? Et d'ailleurs d’où vient itoa() et comment se fait-il quelle ne soit pas standard puisque apparemment tout le monde la connait et l'utilise?
[...]

Parce que la famille de fonction *printf le fait bien pour la plupart des cas. Il manque en effet de quoi afficher un entier en binaire, une proposition a été faite pour introduire les spécificateurs B/b, mais la norme C évolue assez lentement la dernière grosse révision date de 2011 ⇒ C11, la prochaine est prévue pour 2023 ⇒ C23. Et c'est sans doute parce qu'elle est de plus en plus demandée qu'il y a cette proposition.

Dans un C moderne on pourrait écrire la fonction ainsi (pour un code portable) :

Code :

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

1
2
3
4
5
6
7
8
9
10
const char *binary(uintmax_t n)
{
#define BWIDTH ( sizeof(uintmax_t) * CHAR_BIT )
    thread_local static char bin[BWIDTH+1]="";
    char *start=bin+BWIDTH;
    do {
        *--start = n&1?'1':'0';
    } while (n>>=1);
    return start;
}

uintmax_t est un type entier non signé le plus large possible sur la plateforme cible. Le thread_local permet de rendre la fonction thread safe. Pour avoir une chaîne dont tu es propriétaire, il faudrait rajouter un strdup mais cette fonction là n'est pas standard C11 non plus ; une proposition d'ajout à C23 est faite. Oui … lentement je disais ; mais ce n'est pas forcément une mauvaise chose et puis il y a l'inertie due à la base existante. C++ a un rythme beaucoup plus rapide (cycle de 3 ans).

[...c]La syntaxe crochet pour le passage de paramètres permet, il me semble , au compilateur de faire des vérifications de taille ou de type ... mais seulement pour l'unité de compilation en cours - donc assez limité (<- tu es débutant, je te laisse chercher et tester)

En fait pour demander aux compilos (qui comprennent le message gcc, clang, …) que le paramètre passé est un pointeur pointant sur au moins N éléments valides, ce qui implique que le pointeur n'est pas NULL il faut utiliser le mot clé `static` : void foo(size_t size, int array[static size]; par exemple. Ce n'est qu'une indication donné au compilo qui lui permet d'optimiser le code, un peu à l'instar de l'utilisation de `restrict`. Si tu l'utilises mal ensuite …

[Guesset]

Bonjour Foetus,

La fonction ilog2() est erronée, pour 0 elle retourne 0. A défaut d'un hypothétique -oo on peut retourner -1 valeur impossible pour un entier et le tester au retour (même s'il semble plus pertinent de tester la valeur avant d'appeler ilog2).

Le power = powl(2, ilog2(nb)); pique un peu les yeux. Un truc du type power = 1 << ilog2(nb); fait le même boulot à pas cher.

Ceci étant, passer par les log pour ensuite calculer une puissance ne paraît pas nécessaire. Il y a la technique d'effacement des bits à 1 qui fonctionne bien :

Code :

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

1
2
   int pwr2 = 0;
   for(int j = n; j > 0; pwr2 = j) j = j & (j-1);

• 0 et les valeurs négatives renvoient pwr2 = 0
• les autres valeurs retournent la valeur approchée par défaut de la puissance de 2 la plus proche de n

Le code est un peu plus difficile à comprendre mais il est relativement efficace.

Je sais que je suis un peu maniaque. Oui, beaucoup

Salut

[Sve@r]

Ceci étant, passer par les log pour ensuite calculer une puissance ne paraît pas nécessaire. Il y a la technique d'effacement des bits à 1 qui fonctionne bien :

Code :

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

1
2
   int pwr2 = 0;
   for(int j = n; j > 0; pwr2 = j) j = j & (j-1);

Le code est un peu plus difficile à comprendre mais il est relativement efficace.

Exact, il est difficile à comprendre mais il suffit de dérouler à la main et c'est brillant !!!

Ceci dit, il y a un gros soucis car chez-moi (gcc) il semble que l'instruction pwr2=j se fasse une fois de trop. Démo

Code c :

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
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <stdlib.h>
 
int guesset(int n) {
	int pwr2 = 0;
	for (int j = n; j > 0; pwr2 = j) {
		j = j & (j-1);
	}
	return pwr2;
}
 
int guesset2(int n) {
	int pwr2 = n;
	for (int j = n; j > 0; pwr2 = j) {
		j = j & (j-1);
		if (j == 0) break;
	}
	return pwr2;
}
 
int main(int argc, char *argv[]) {
	for (int i=1; i < argc; i++) {
		int n=atoi(argv[i]);
		printf("%d: %d - %d\n", n, guesset(n), guesset2(n));
	}
}

La première fonction (la tienne) renvoie toujours 0. Pourtant du printf() dans la boucle montre que pwr2 prend la bonne valeur. Mais quand on quitte la boucle, il vaut alors 0.
La seconde fonction renvoie la bonne valeur.

De là j'ai modifié ton code de cette façon

Code c :

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

1
2
3
4
5
6
7
8
9
int guesset3(int n) {
	int pwr2 = n;
	int j=n;
	while (1) {
		if (j == 0) return pwr2;
		pwr2=j;
		j&=(j-1);
	}
}

[foetus]

La fonction ilog2() est erronée, pour 0 elle retourne 0.

J'ai repris l'algo de @WhiteCrow pour aller au + vite. C'était juste pour donner 1 idée, pas faire 1 algo précis.
Et effectivement c'est "une fonction qui renvoie le rang (0=LSB) du bit le plus significatif positionné à 1 et 0 pour la valeur 0" (<- c'est le message de @WhiteCrow)
Moi je dirais que c'est le log binaire arrondi à l'inférieur
L'avantage, c'est que pour mon algo, cela m'évite d'avoir des 0 à gauche. Et c'est à peu près le cas également pour l'algo de @WhiteCrow.

Le power = powl(2, ilog2(nb)); pique un peu les yeux. Un truc du type power = 1 << ilog2(nb); fait le même boulot à pas cher.

je tanne les autres sur le nombre d'appels
et en +, j'en parle avec les décalages binaires.
J'ai modifié mon code.

Ceci étant, passer par les log pour ensuite calculer une puissance ne paraît pas nécessaire. Il y a la technique d'effacement des bits à 1 qui fonctionne bien

Moi, je pensais + à 1 fonction qui fasse les 2 calculs ... au détriment du nombre d'opérations et 1 peu de la logique.

Et comme le dit @Sve@r et comme tu l'as remarqué, "le nombre de bits nécessaires pour représenter un entier n sera ilog2(n)+1" ou maintenant compute_XXX(n, RETURN_NB_BITS)+1 (<- c'est le message de @WhiteCrow)

1 code du style

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
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
#include <stdio.h>
#include <stdlib.h>
 
 
typedef enum e_RETURN {
    RETURN_NB_BITS = 0, // minus 1
    RETURN_LAST_POWER
} t_return;
 
 
size_t compute_XXX(size_t nb, t_return ret) {
    size_t val;
 
    if (nb > 1) {
        size_t acc, mul;
 
        acc = mul = val = ((ret == RETURN_NB_BITS)?1:2);
        nb >>= 1;
 
        while (nb >>= 1) {
            val += acc;
            acc *= mul;
        }
    } else {
        val = ((ret == RETURN_NB_BITS)?0:1);
    }
 
    return val;
}
 
 
/*****************************************************************************/
/***********************************  Main  **********************************/
/*****************************************************************************/
 
int main(int argc, char** argv)
{
    size_t nb;
 
    for(nb=0; nb < 129; ++nb) {
        printf("%3lu: %lu %lu\n", nb, compute_XXX(nb, RETURN_NB_BITS), compute_XXX(nb, RETURN_LAST_POWER));
    }
 
 
    return EXIT_SUCCESS;
}

[WhiteCrow]

Alors effectivement,

Bonjour Foetus,

La fonction ilog2() est erronée, pour 0 elle retourne 0. A défaut d'un hypothétique -oo on peut retourner -1 valeur impossible pour un entier et le tester au retour (même s'il semble plus pertinent de tester la valeur avant d'appeler ilog2).
[...]

C'est un nom mal choisi. Mais comme le rappelle Fœtus

J'ai repris l'algo de @WhiteCrow pour aller au + vite. C'était juste pour donner 1 idée, pas faire 1 algo précis.
Et effectivement c'est "une fonction qui renvoie le rang (0=LSB) du bit le plus significatif positionné à 1 et 0 pour la valeur 0" (<- c'est le message de @WhiteCrow)
Moi je dirais que c'est le log binaire arrondi à l'inférieur
L'avantage, c'est que pour mon algo, cela m'évite d'avoir des 0 à gauche. Et c'est à peu près le cas également pour l'algo de @WhiteCrow.

J'en ai donné une définition :

Si on tient à compter le nombre de bits qu'il faut pour représenter un entier classiquement il faut passer par un log entier en base 2. ilog2 est une fonction qui renvoie le rang (0=LSB) du bit le plus significatif positionné à 1 et 0 pour la valeur 0.

J'aurais sans doute dû l'appeler binary_width en rajoutant 1 …

[Guesset]

Bonjour Sve,

...Ceci dit, il y a un gros soucis car chez-moi (gcc) il semble que l'instruction pwr2=j se fasse une fois de trop...

Bizarre. Je n'avais pas testé. Je pense qu'en explicitant la séquence cela ne devrait pas avoir cet effet.
Par ailleurs, dans une fonction on pourra allègrement se passer de j en utilisant n à la place.

Code C :

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

1
2
3
4
5
6
7
8
int pwr2of(int n) {
   int pwr2 = 0;
   while (n > 0) {
      pwr2 = n;
      n &= n-1;
   }
   return pwr2;
}

Salut et merci de ton retour.

[Guesset]

Bonjour WhiteCrow,

Si on tient à compter le nombre de bits qu'il faut pour représenter un entier classiquement il faut passer par un log entier en base 2. ilog2 est une fonction qui renvoie le rang (0=LSB) du bit le plus significatif positionné à 1 et 0 pour la valeur 0.

Si la fonction doit retourner le rang du MSB elle retournera 0 pour n == 1 == 2⁰. Elle devra donc retourner une autre valeur pour n == 0, -1 par exemple. C'est vrai que le nombre de bits nécessaires = rang du MSB +1 pourrait convenir même pour 0 mais reporterait le problème pour avoir l'approximation 2^a par défaut de n.

Rien n'est simple

Salut

[WhiteCrow]

@Guesset
C'est juste une convention utile dans ce cas, un peu de la manière où l'on définit 0⁰ valant 0 ou 1 suivant le contexte et l'utilité. Mais bon à la place de bwidth on aurait pu nommer la fonction binary_width_to_encode. Le tout est d'être clair dans la définition pour que ceux qui la lisent puissent la comprendre.