Newsgroup: it.comp.lang.c
Titolo: Problema difficile, per me

Ho un numero intero x, devo creare una funzione che restituisca 1 se x 
può essere rappresentato come un numero intero complemento a due, 
ad n-bit, 0 altrimenti.
Il vincolo su n è che 1<=n<=32.  
Esempio: funzione(5,3)=0
funzione(-4,3)=1
E' possibile usare solo i seguenti operatori: ! ~ & ^ | + << >>
Non sono ammessi cicli e if


Basta che ci pensi un secondo..
Su n bit, qual'è il massimo (o il minimo) numero che puoi rappresentare? :)
 
Ciao!


Il minimo dovrebbe essere -2^(n-1) ed il massimo 2^(n-1)+1, quindi
-4 dovrebbe essere 1100 
+5 dovrebbe essere 0101
 
entrambi li posso rappresentare con 3 bit più il bit di segno
 
A parte, non ho molta esperienza con gli operatori bitwise
 

 A parte, non ho molta esperienza con gli operatori bitwise
 
Basta fare un po' di prove.
 
Ti do un altro suggerimento... inizia a vedere solo i positivi e solo i
negativi, semplifica un po' il ragionamento.
 
Ciao!

 Ok, quindi -4 non ci sta (ne servono minimo 4) e 5 sì.
 
Però funzione(-4,3)=1, e quindi secondo questa funzione 3 bit sono 
sufficienti per esprimere -4.
 
 

 sufficienti per esprimere -4.
 
Hai 3 bit a disposizione, giusto? Con il segno, giusto? Count down!
 
3  = 011
2  = 010
1  = 001
0  = 000
-1 = 111
-2 = 110
-3 = 101
-4 = 100
 
 


Non mi trovo, -4 dovrebbe essere 1100.
Infatti, 4=0100 --> complemento a uno dei bits -> 1011 --> aggiungo 1 --> 
1100
 
 

 1100
 
Io sto dicendo che per -4 bastano 3 bit col segno, non che gli stessi 
bastano per +4, quindi:
 
4 = 100 (valore assoluto, senza segno, niente 0 davanti)
Poi complemento = 011
Poi sommi 1 = 100
 
 
 
 
 
 
 

 entrambi li posso rappresentare con 3 bit più il bit di segno
[..]
 
Qui hai un po' di confusione, se n = 3 significa che puoi usare solo
3 bits, non 3 più quello del segno. Quindi non puoi rappresentare
il 5 come 0101, ma semplicemente 101 (appunto 3 bits). Beh direi che
la risposta te la sei già data da solo, in pratica devi solo testare
che il numero x stia nell'intervallo no?
 
/* solo C99 */
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
 
int c(int32_t x, uint32_t n)
{
         return (x <= (1 << n - 1) - 1) && (x >= - (1 << n - 1));
}
 
void e(int32_t x, uint32_t n)
{
         printf("\nnumero = %" PRId32 ", bits = %" PRIu32 ","
                " intervallo [%" PRId32 ", %" PRId32 "]: ",
                x, n, - (1 << n - 1), (1 << n - 1) - 1);
         if (!c(x, n)) printf("NON ");
         puts("esiste complemento a due");
}
 
int main(void)
{
         e(5, 3);
         e(-4, 3);
         e(6, 4);
         e(-10, 2);
         e(1, 2);
 
         return 0;
}
 
-- 
Vincenzo Mercuri

 }
[..]
 
da sostituire con:
 
int c(int32_t x, uint32_t n)
{
         return (x <= (int32_t)(1 << n - 1) - 1) &&
                (x >= - (int32_t)(1 << n - 1));
}
 
non ho fatto i vari test di overflow, e neanche che n stia in [1, 32],
quello meglio non farlo nella funzione c(), ma in quella chiamante.
 
-- 
Vincenzo Mercuri

 }
 
Ok, ora mi sembra alquanto più chiaro, ma purtroppo posso usare solo i 
seguenti operatori:   ! ~ & ^ | + << >>
 
Potrei sostituire il confronto tra due quantità a e b con il valore del 
segno della loro differenza a-b.
Ma come faccio a ricavare il bit di segno usando gli operatori bitwise ?
 


 
Se per esempio vuoi confrontare a 1 il bit in posizione "pos", puoi
scrivere:
 
	numero & 1 << pos
 
che ti dà un valore "true" se il bit è 1. Ricorda però che gli operatori
bitwise è opportuno che abbiano operandi di tipo "unsigned" o puoi
ritrovarti con valori senza significato, oppure con undefined-behavior.
 
 
-- 
Vincenzo Mercuri


 
Con posizione intendo da 0 a 7 in un byte, per intenderci. C'è questa
bella pagina su internet che puo' sempre servire:
http://graphics.stanford.edu/~seander/bithacks.html
 
magari non in questa occasione, ma puo' tornare sempre utile.
 
-- 
Vincenzo Mercuri


azzeri la parte relativa ai bit - uno, gli altri bit possono essere o 
tutti uno o tutti zero e allora il numero può essere rappresentato, ogni 
altro valore significa che il numero eccede i bit dati.
Ciao
 
mask = ~((1 << (b - 1)) - 1)
v = n & mask
 
v1 = !v // se v1 -> 1 allora v = 0
v2 = !(v ^ mask) // se v2 -> 1 allora v = mask
 
return v1 | v2