Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Problema difficile, per me
39 views
Skip to first unread message
francesco
Apr 23, 2013, 6:25:46 AM4/23/13
to
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
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
fma...@gmail.com
Apr 23, 2013, 6:30:14 AM4/23/13
to
Su n bit, qual'è il massimo (o il minimo) numero che puoi rappresentare? :)
Ciao!
francesco
Apr 23, 2013, 7:21:38 AM4/23/13
to
-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
fma...@gmail.com
Apr 23, 2013, 7:40:40 AM4/23/13
to
On Tuesday, April 23, 2013 1:21:38 PM UTC+2, francesco wrote:
> Il Tue, 23 Apr 2013 03:30:14 -0700, fmassei ha scritto:
> > On Tuesday, April 23, 2013 12:25:46 PM UTC+2, francesco wrote:
> >> 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?
> > :)
>
> Il Tue, 23 Apr 2013 03:30:14 -0700, fmassei ha scritto:
> > On Tuesday, April 23, 2013 12:25:46 PM UTC+2, francesco wrote:
> >> 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?
> > :)
>
> 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
>
Ok, quindi -4 non ci sta (ne servono minimo 4) e 5 sì.
> -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
Ti do un altro suggerimento... inizia a vedere solo i positivi e solo i
negativi, semplifica un po' il ragionamento.
Ciao!
francesco
Apr 23, 2013, 9:16:14 AM4/23/13
to
Il Tue, 23 Apr 2013 04:40:40 -0700, fmassei ha scritto:
> On Tuesday, April 23, 2013 1:21:38 PM UTC+2, francesco wrote:
>> Il Tue, 23 Apr 2013 03:30:14 -0700, fmassei ha scritto:
>> > On Tuesday, April 23, 2013 12:25:46 PM UTC+2, francesco wrote:
>> >> 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?
>> > :)
>>
>> 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
>>
>>
> 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
> On Tuesday, April 23, 2013 1:21:38 PM UTC+2, francesco wrote:
>> Il Tue, 23 Apr 2013 03:30:14 -0700, fmassei ha scritto:
>> > On Tuesday, April 23, 2013 12:25:46 PM UTC+2, francesco wrote:
>> >> 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?
>> > :)
>>
>> 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
>>
>>
> Ok, quindi -4 non ci sta (ne servono minimo 4) e 5 sì.
sufficienti per esprimere -4.
ReadOnly
Apr 23, 2013, 9:54:45 AM4/23/13
to
Il 23/04/2013 15:16, francesco ha scritto:
> Però funzione(-4,3)=1, e quindi secondo questa funzione 3 bit sono
> sufficienti per esprimere -4.
Hai 3 bit a disposizione, giusto? Con il segno, giusto? Count down!
> Però funzione(-4,3)=1, e quindi secondo questa funzione 3 bit sono
> sufficienti per esprimere -4.
3 = 011
2 = 010
1 = 001
0 = 000
-1 = 111
-2 = 110
-3 = 101
-4 = 100
francesco
Apr 23, 2013, 10:26:08 AM4/23/13
to
Infatti, 4=0100 --> complemento a uno dei bits -> 1011 --> aggiungo 1 -->
1100
ReadOnly
Apr 23, 2013, 10:59:38 AM4/23/13
to
Il 23/04/2013 16:26, francesco ha scritto:
>> 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
Io sto dicendo che per -4 bastano 3 bit col segno, non che gli stessi
>> 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
bastano per +4, quindi:
4 = 100 (valore assoluto, senza segno, niente 0 davanti)
Poi complemento = 011
Poi sommi 1 = 100
Vincenzo Mercuri
Apr 23, 2013, 4:28:19 PM4/23/13
to
On 23/04/2013 13:21, francesco wrote:
> Il Tue, 23 Apr 2013 03:30:14 -0700, fmassei ha scritto:
>
>> On Tuesday, April 23, 2013 12:25:46 PM UTC+2, francesco wrote:
>>> 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
Il valore del massimo non è corretto, è 2^(n-1)-1.
> Il Tue, 23 Apr 2013 03:30:14 -0700, fmassei ha scritto:
>
>> On Tuesday, April 23, 2013 12:25:46 PM UTC+2, francesco wrote:
>>> 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
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
Vincenzo Mercuri
Apr 23, 2013, 4:46:47 PM4/23/13
to
On 23/04/2013 22:28, Vincenzo Mercuri wrote:
[..]
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
[..]
> int c(int32_t x, uint32_t n)
> {
> return (x <= (1 << n - 1) - 1) && (x >= - (1 << n - 1));
> }
[..]
> {
> return (x <= (1 << n - 1) - 1) && (x >= - (1 << n - 1));
> }
da sostituire con:
int c(int32_t x, uint32_t n)
{
(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
francesco
Apr 23, 2013, 2:50:31 PM4/23/13
to
>
> 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));
> }
Ok, ora mi sembra alquanto più chiaro, ma purtroppo posso usare solo i
> 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));
> }
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 ?
Vincenzo Mercuri
Apr 23, 2013, 5:13:41 PM4/23/13
to
On 23/04/2013 20:50, francesco wrote:
[..]
>
> 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 ?
>
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
Vincenzo Mercuri
Apr 23, 2013, 5:31:04 PM4/23/13
to
On 23/04/2013 23:13, Vincenzo Mercuri wrote:
> On 23/04/2013 20:50, francesco wrote:
> [..]
>
>>
>> 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
>
Con posizione intendo da 0 a 7 in un byte, per intenderci. C'è questa
> On 23/04/2013 20:50, francesco wrote:
> [..]
>
>>
>> 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
>
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
logicmind
Apr 24, 2013, 2:38:58 AM4/24/13
to
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
0 new messages