[C] Estrazione bit

[k_mishima]

Salve, stavo provando a fare 1 esercizio ma mi risulta un po difficile, potreste aiutarmi? (scusate se rompo di nuovo)

La traccia è:

Scrivere 1 function C per estrarre dalla variabile intera A i k bit più o meno significativi dove k e A sono parametri di input usando (1) una maschera opportuna; (2) una maschera e operatori di shif (<< o >>)

Già di per se la traccia non mi era chiara perchè la maschera non ho capito cos'è, poi per quanto riguarda l'estrazione nemmeno ho capito, cioè diciamo che io in input do' 4 in binario sarebbe

00000000.00000000.00000000.00000100

per estrarre i 3 piu' significativi devo estrarre questo in grassetto?

00000000.00000000.00000000.00000100?

e le meno significative devo estrarre questo?

00000000.00000000.00000000.00000100?

E che si intende per estrazione? Devono essere visualizzate solo quelle 3 cifre? Mi spieghereste pure cos'è una maschera? Scusate ma dalle slide della prof non si capisce

[cionci]

La maschera è un intero che rappresentato in binario ha un 1 in tutti i bit che vuoi estrarre, ed uno 0 negli altri bit...

Se sai l'aritmetica binaria saprai che utilizzando l'and fra la maschera ed i dato, il risultato sarà composto da tutti zero dove la maschera ha zero e il valore del dato dove la maschera ha gli uno...

I K bit meno significativi sono i K più a destra (nella notazione classica), i K più significativi sono i K più a sinistra...

[andbin]

Originariamente inviato da k_mishima

per estrarre i 3 piu' significativi devo estrarre questo in grassetto?

00000000.00000000.00000000.00000100?

e le meno significative devo estrarre questo?

00000000.00000000.00000000.00000100?

No no. Dato un numero a N bit, il bit più significativo è quello più a sinistra (il bit N-1) e il meno significativo è quello più a destra (il bit 0).

[k_mishima]

ahhh, ok, capito, era piu' facile di quello che pensavo, credevo fosse chissà quale mostruosa cosa...

cmq ho scritto un po' il codice ma non va...

mi da sempre lo stesso risultato X=65356

sara' per colpa di questo forse
5 n:\ciisem~1\lv1\4masch~1\maschera.c
warning: return type of `main' is not `int'

#include <stdio.h>
int PIU_SIGNIFICATIVI(int A,int k);
int MENO_SIGNIFICATIVI(int A,int k);
void main()
{
     int A,k,X;
     short scelta;

     puts("Digita un valore A");
     scanf("%d,&A");

     puts("Digita quanti bit vuoi estrarre (max 32)");
     scanf("%d,&k");

     puts("Digita se estrarre i bit piu' significativi o meno significativi");
     puts("Piu' significativi [0]");
     puts("Meno significativi [1]");

     scanf("%ld,&scelta");

     while ((scelta==0 || scelta==1))
     {
     puts ("Scelta errata, riprovare");
     scanf("%ld,&scelta");
     }

     if (scelta==0)
     X=PIU_SIGNIFICATIVI(A,k);

     else if (scelta==1)
     X=MENO_SIGNIFICATIVI(A,k);

     printf("Risultato X=%d\n",X);
     system("pause");
}

int PIU_SIGNIFICATIVI(int A,int k)
{
   int mask;
   short i;

   //Creazione maschera
   for (i=1;i<k;i++)
   mask=mask*2;
   mask--;

   mask<<(sizeof(int)*8-k);

   return mask&A;
}

int MENO_SIGNIFICATIVI(int A,int k)
{
     short b;
     int mask=0;

     for(b=1;b<=k;b++)
     mask=mask<<1|1;
     return mask&A;
}

manco il while va, esce il risultato qualsiasi numero metto
consigli?

[sottovento]

Ciao,
- per quanto riguarda il ciclo while, quello che hai scritto, in sintesi e': "se i dati sono corretti, ritenta". Probabilmente intendevi il contrario (a meno ovviamente di una svista mia);

- Sarebbe meglio (ma e' solo un parere personale) se il bit meno significativo fosse 0 e non 1. Questo per due motivi:
1 - e' piu' semplice;
2 - fanno tutti cosi', per cui e' quello che ci si aspetta;

- Il codice per MENO_SIGNIFICATIVI sembra OK. Il codice per PIU_SIGNIFICATIVI e' particolarmente strano. E' quello che non funziona?
In piu' non hai inizializzato la mask, per cui il risultato sara' comunque indeterminato.
Suggerimento: fai la stessa cosa di MENO_SIGNIFICATIVI, inizializzi la variabile mask a 0x80000000 e poi shift a destra


Sottovento

[cionci]

mask<<(sizeof(int)*8-k);
Questo operazione non fa niente dato che non hai assegnato il risultato...
Inltre: mask=mask*2 equivale a fare: mask = mask << 1;

Le maschere le puoi creare con gli shift...

Data una maschera (che può avere già dei bit a 1) per aggiungere un 1 in una posizione qualsiasi devi fare lo shift sinistra del numero 1 di N posizioni corrispondenti al bit che vuoi a 1 e poi fare un or con la maschera...

[k_mishima]

grazie per gli aiuti, ho aggiustato il while, e per quanto riguarda sempre lo stesso risultato, avevo sbagliato un " nelle scanf (il compilatore mi sa che è vecchio non lo segnalava (dev 4)

ora il codice è cosi'

#include <stdio.h>
int PIU_SIGNIFICATIVI(int A,int k);
int MENO_SIGNIFICATIVI(int A,int k);
void div_successive(int Numero_X, int base, int R_inv[], int *n);
main()
{

     int A,k,X,n,Array[32];
     short i,scelta;

     puts("Digita un valore A");
     scanf("%d",&A);

     puts("Digita quanti bit vuoi estrarre (max 32)");
     scanf("%d",&k);

     puts("Digita se estrarre i bit piu' significativi o meno significativi");
     puts("Meno significativi [0]");
     puts("Piu' significativi [1]");

     scanf("%hd",&scelta);

     while (!(scelta==0 || scelta==1))
     {
     puts ("Scelta errata, riprovare");
     scanf("%hd",&scelta);
     }

     if (scelta==0)
     X=MENO_SIGNIFICATIVI(A,k);

     else if (scelta==1)

     X=PIU_SIGNIFICATIVI(A,k);


     printf("Risultato decimale X=%d\n",X);

     div_successive (X,2,Array,&n);
     printf("Risultato binario X=");
     for (i=0;i<n;i++)
     printf("%d",Array[i]);
     printf("\n");
     system("pause");
}

int PIU_SIGNIFICATIVI(int A,int k)
{
   int mask=1;
   short i,j;

   //Creazione maschera
   for (i=0;i<k;i++)
   mask=mask<<1;
   mask--;

   printf("Maschera_1: %d\n\n",mask);
   mask=mask<<(sizeof(int)*8-k);

   printf("Maschera_2: %d\n",mask);

   return mask&A;
}

int MENO_SIGNIFICATIVI(int A,int k)
{
     short b;
     int mask=0;

     for(b=1;b<=k;b++)
     mask=mask<<1|1;
     return mask&A;
}



void div_successive(int Q, int B, int R_inv[], int *n)
{
	int Q1,j,i;
	int R[30];
	j=-1;

/* Calcolo resti */
	while (Q>0)
	{
		j+=1;
		Q1=Q/B;
		R[j]=Q-Q1*B;
		Q=Q1;
	}

/* Inversione */
	for (i=0;i<=j;i++)
	{
		R_inv[i]=R[j-i];
		R_inv[j]=R[j-i];
	}
	*n=j+1;
}

La parte meno significativa funziona, quella piu' no, il passaggio mask=mask<<(sizeof(int)*8-k); deve avere qualche errore, pechè non da il risultato corretto.

@cionci
la maschera l'ho creata in 2 modi, questo mask=mask<<1|1; è quello che intendevi tu vero?

@sottovento
Perchè devo salvare la variabile mask a 0x80000000 e poi shiftare a destra? Non è piu' comodo il mio metodo?

P.s. ma per mostrare i bit, non c'è un metodo piu' semplice di quella function per le divisioni successive enorme?

[cionci]

Originariamente inviato da k_mishima

@cionci
la maschera l'ho creata in 2 modi, questo mask=mask<<1|1; è quello che intendevi tu vero?

No, te praticamente in quel modo metti un 1 al bit zero e shifti a sinistra il contenuto precedente (e quindi gli uno) già immessi... Va bene anche come l'hai fatto te, ma io intendevo questo:

for(b = 0; b < k; b++)
mask |= 1 << b;

Stai attento ai cicli for, in questo caso non cambia niente, ma non prendere l'abitudine di farli partire da 1 e farli arrivare a k...prendi invece l'abitudine di farli come ti ho scritto sopra...

[sottovento]

int PIU_SIGNIFICATIVI(int A,int k)
{
     return (unsigned)(((int)0x80000000 >> k) & A) >> (32 - k);
}

Semplice, no?

[andbin]

Originariamente inviato da sottovento

int PIU_SIGNIFICATIVI(int A,int k)
{
     return (unsigned)(((int)0x80000000 >> k) & A) >> (32 - k);
}

Semplice, no?

Come no ...
Più semplicemente:

int higher_bits (int value, int bits)
{
    return (int)(((unsigned int) value) >> (32-bits));
}

[sottovento]

Originariamente inviato da andbin

Come no ...
Più semplicemente:

int higher_bits (int value, int bits)
{
    return (int)(((unsigned int) value) >> (32-bits));
}

Acc, mi era scappata
A questo punto, compilatore permettendo, puoi togliere l'ultimo cast in ordine di esecuzione. Rischioso, pero'...

[cionci]

Gli si chiedeva di usare una maschera

[sottovento]

Originariamente inviato da cionci

Gli si chiedeva di usare una maschera

Infatti c'e'.
Beh, nella soluzione ottima, quella di AndBin no, ma scommetto che il prof non c'aveva pensato...

[k_mishima]

grazie, quest'esercizio va sempre meglio

@andbin
ottimo il tuo suggerimento, pero' devo usare la maschera, altrimenti non seguo il testo, cmq me lo sono segnato.

@cionci
si ho messo apposta quell'1 nel for perchè b era un contatore e un'indice di 1 array, cmq l'ho cambiato in 0, in effetti è sempre meglio partire da 0

@sottovento
lol, troppo complicato

cmq ora ho fatto cosi' e viene, l'errore credo fosse nel sizeof, infatti se metto 32 a mano, il risultato viene...

#include <stdio.h>
int PIU_SIGNIFICATIVI(int A,int k);
int MENO_SIGNIFICATIVI(int A,int k);
void div_successive(int Numero_X, int base, int R_inv[], int *n);
main()
{

     int A,k,X,n,Array[32];
     short i,scelta;

     puts("Digita un valore A (max 4294967295)");
     scanf("%d",&A);

     puts("Digita quanti bit vuoi estrarre (max 32)");
     scanf("%d",&k);

     puts("Digita se estrarre i bit piu' significativi o meno significativi");
     puts("Meno significativi [0]");
     puts("Piu' significativi [1]");

     scanf("%hd",&scelta);

     while (!(scelta==0 || scelta==1))
     {
         puts ("Scelta errata, riprovare");
         scanf("%hd",&scelta);
     }

     if (scelta==0)
     X=MENO_SIGNIFICATIVI(A,k);

     else if (scelta==1)
     X=PIU_SIGNIFICATIVI(A,k);


     printf("Risultato decimale X=%u\n",X);

        div_successive (X,2,Array,&n);
        printf("Risultato binario X=");
        for (i=0;i<n;i++)
        printf("%d",Array[i]);
        printf("\n");

        system("pause");
}

int PIU_SIGNIFICATIVI(int A,int k)
{
     int mask=1;
     //Creazione maschera
     mask=mask<<k;
     mask--;

     mask=mask<<(32-k);
     printf("%u",mask);
     printf("\n");

 //  return (int)(((unsigned int) A)>>(32-k));
     return A&mask;
}

int MENO_SIGNIFICATIVI(int A,int k)
{
     short b;
     int mask=0;

     for(b=0;b<k;b++)
     mask=mask<<1|1;
     return mask&A;
}



void div_successive(int Q, int B, int R_inv[], int *n)
{
	int Q1,j,i;
	int R[30];
	j=-1;


/* Calcolo resti */
	while (Q>0)
	{
		j+=1;
		Q1=Q/B;
		R[j]=Q-Q1*B;
		Q=Q1;
	}

/* Inversione */
	for (i=0;i<=j;i++)
	{
		R_inv[i]=R[j-i];
		R_inv[j]=R[j-i];
	}
	*n=j+1;
}

L'unico problema è ora la visualizzazione in binario

Tipo se deve scrivere 01000 scrive 1000, oppure se il numero è negativo (bit + significativo alto) la function non va perchè funziona solo per numeri maggiori di 0 (per via della condizione di questo while)

/* Calcolo resti */
	while (Q>0)
	{
		j+=1;
		Q1=Q/B;
		R[j]=Q-Q1*B;
		Q=Q1;
	}

Ma non avete una function migliore per rappresentare il binario? Fa pena questa che ho fatto io
Non potevano mettere direttamente un modo tipo %qualcosa? lol

[andbin]

Originariamente inviato da k_mishima

@andbin
ottimo il tuo suggerimento, pero' devo usare la maschera, altrimenti non seguo il testo, cmq me lo sono segnato.

Ok, però se hai notato bene, la soluzione di sottovento usa proprio una maschera! Lo shift a destra di un int 0x80000000 causa il mantenimento del bit di segno a 1, che pertanto si estende verso destra di k bit.

Originariamente inviato da k_mishima

Ma non avete una function migliore per rappresentare il binario? Fa pena questa che ho fatto io
Non potevano mettere direttamente un modo tipo %qualcosa? lol

Guarda, se ne parla giusto in <questo> thread di questi ultimi giorni.
In più vedi la mia risposta in <questo> thread.

[k_mishima]

#include <stdio.h>
int PIU_SIGNIFICATIVI(int A,int k);
int MENO_SIGNIFICATIVI(int A,int k);
void dec2bin(unsigned int inp, char binstr[32]);
main()
{

     int A,k,X,n;
     short i,scelta;
     char Array[32];

     puts("Digita un valore A (max 4294967295)");
     scanf("%d",&A);

     puts("Digita quanti bit vuoi estrarre (max 32)");
     scanf("%d",&k);

     puts("Digita se estrarre i bit piu' significativi o meno significativi");
     puts("Meno significativi [0]");
     puts("Piu' significativi [1]");

     scanf("%hd",&scelta);

     while (!(scelta==0 || scelta==1))
     {
         puts ("Scelta errata, riprovare");
         scanf("%hd",&scelta);
     }

     if (scelta==0)
     {
      X=MENO_SIGNIFICATIVI(A,k);
      dec2bin (X,Array);
      printf("Risultato binario X=");
      for (i=k-1;i>=0;i--)
      printf("%c",Array[i]);
     }

     else if (scelta==1)
     {
      X=PIU_SIGNIFICATIVI(A,k);
      dec2bin (X,Array);
      printf("Risultato binario X=");
       for (i=31;i>=(31-k);i--)
        printf("%c",Array[i]);
     }

     printf("\n");
     system("pause");
}

int PIU_SIGNIFICATIVI(int A,int k)
{
     int mask=1;
     //Creazione maschera
     mask=mask<<k;
     mask--;

     mask=mask<<(32-k);

 //  return (int)(((unsigned int) A)>>(32-k));
     return A&mask;
}

int MENO_SIGNIFICATIVI(int A,int k)
{
     short b;
     int mask=0;

     for(b=0;b<k;b++)
     mask=mask<<1|1;
     return mask&A;
}


void dec2bin(unsigned int inp, char binstr[32])
{
    int i;
    for (i = 0; i < 32; i++, inp >>= 1)
        binstr[i] = (inp & 1) + '0';
}

Finalmente finita, dopo ore e ore di prove

@andbin
carina la tua function per il dec2bin, molto compatta, peccato che pero' che non inverta pure l'array che deve essere stampato al contrario, altrimenti sarebbe perfetta

[andbin]

Originariamente inviato da k_mishima

@andbin
carina la tua function per il dec2bin, molto compatta, peccato che pero' che non inverta pure l'array che deve essere stampato al contrario, altrimenti sarebbe perfetta

È così perché l'autore di quel thread aveva chiesto di non usare stringhe (solo un array di char non terminato dal nullo) e che in binstr[0] ci fosse il bit meno significativo (non so per quale motivo).

Vuoi gestire una stringa visualizzabile direttamente? Ecco:

void dec2bin(unsigned int inp, char *binstr)
{
    int i;
    for (i = 0; i < 32; i++, inp >>= 1)
        binstr[31-i] = (inp & 1) + '0';
    binstr[32] = '\0';
}

Quindi nel main dichiari un array di char di 33 caratteri (adesso c'è anche il nullo), quindi chiami la funzione, e poi stampi direttamente con printf.

[k_mishima]

ah, ora vedendo il tuo codici vedo che in effetti è inutile invertire l'array di caratteri, basta salvarlo direttamente al contrario

/* Scrivere 1 function C per estrarre dalla variabile intera A i k bit più o meno
significativi dove k e A sono parametri di input usando (1) una maschera opportuna;
(2) una maschera e operatori di shif (<< o >>) */

#include <stdio.h>
int PIU_SIGNIFICATIVI(int A,int k);
int MENO_SIGNIFICATIVI(int A,int k);
void dec2bin(unsigned int inp, char binstr[32]);
main()
{

     int A,k,X,n;
     short i,scelta;
     char Array[32];

     puts("Digita un valore A (max 4294967295)");
     scanf("%d",&A);

     puts("Digita quanti bit vuoi estrarre (max 32)");
     scanf("%d",&k);

     puts("Digita se estrarre i bit piu' significativi o meno significativi");
     puts("Meno significativi [0]");
     puts("Piu' significativi [1]");

     scanf("%hd",&scelta);

     while (!(scelta==0 || scelta==1))
     {
         puts ("Scelta errata, riprovare");
         scanf("%hd",&scelta);
     }

     if (scelta==0)
     {
      X=MENO_SIGNIFICATIVI(A,k);
      dec2bin (X,Array);
      printf("Risultato binario X=");
      for (i=31;i>(31-k);i--)
      printf("%c",Array[i]);
     }

     else if (scelta==1)
     {
      X=PIU_SIGNIFICATIVI(A,k);
      dec2bin (X,Array);
      printf("Risultato binario X=");
       for (i=0;i<k;i++)
        printf("%c",Array[i]);
     }

     printf("\n");
     system("pause");
}

int PIU_SIGNIFICATIVI(int A,int k)
{
     int mask=1;
     //Creazione maschera
     mask=mask<<k;
     mask--;

     mask=mask<<(32-k);

 //  return (int)(((unsigned int) A)>>(32-k));
     return A&mask;
}

int MENO_SIGNIFICATIVI(int A,int k)
{
     short b;
     int mask=0;

     for(b=0;b<k;b++)
     mask=mask<<1|1;
     return mask&A;
}


void dec2bin(unsigned int inp, char binstr[32])
{
    int i;
    for (i = 0; i < 32; i++, inp >>= 1)
        binstr[31-i] = (inp & 1) + '0';
}

Cosi' è veramente perfetto. Ma perchè avrei dovuto usare stringhe? Va cosi' bene con i char