Anonimo
Anonimo ha chiesto in Computer e InternetProgrammazione e Design · 1 mese fa

Problema in C?

Non riesco a capire un esempio riportato in un manuale C.

unsigned int getbits(unsigned int x, int p, int n) { return (x >> (p + 1 - n)) & ~(~0 << n); } Il programma restituisce n bit (allineati a destra) di x a partire dalla posizione p. Io so come funzionano i vari operatori ecc. Per & o | ma non riesco a capire minimamente cosa l'esercizio!! Cosa serve shiftare in questo caso? 10 punti al migliore per chi mi sappia aiutare!!

1 risposta

Classificazione
  • 1 mese fa
    Migliore risposta

    Partiamo dal capire chi è l'operando di destra: ~(~0 << n): se immagini che gli interi senza segno siano rappresentati su 32 bit allora. 

    0 = 00000000000000000000000000000000 

    Pertanto:

    ~0 = 11111111111111111111111111111111

    Immagina di fissare n=6, p = 12, e prendiamo

         ³¹ ³⁰ ²⁹ ²⁸ ²⁷ ²⁶ ²⁵ ²⁴ ²³ ²² ²¹ ²⁰ ¹⁹ ¹⁸ ¹⁷ ¹⁶ ¹⁵ ¹⁴ ¹³ ¹² ¹¹ ¹⁰ ⁹ ⁸ ⁷ ⁶ ⁵ ⁴ ³ ² ¹ ⁰

    x = 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1

    Numero generato completamente a caso con un generatore di numeri casuali, 

    Adesso l'effetto di "<< n" è quello di shiftare il tutto a sinistra di n posizioni, nel nostro caso particolare di n=6, ottenendo:

    ~0 << n = 11111111111111111111111111000000

    Ossia l'espressione tra parentesi produce una sequenza di uni seguita da n zeri. Dopodiché dobbiamo applicare nuovamente l'operando ~, ottenendo

    ~( ~0 << n ) = 0000000000000000000000000111111

    Invece l'operando di destra prende il contenuto di x e shifta il tutto a destra di p - (n-1) posizioni. allora nel nostro caso p - (n-1) = 12 - 5 = 7: il membro di sinistra diventa quindi

                                                                               

    x >> (p + 1 - n) =  00000001001100000111111111010001 

    A questo punto non rimane che applicare l'and logico, ottenendo

        (x >> (p + 1 - n)) & ~(~0 << n) 

     = 00000001001100000111111111010001 &

        0000000000000000000000000111111 = 

       -----------------------------------------------------

        0000000000000000000000000010001 

    Quindi tutta questa espressione permette di recuperare gli n bit precedenti al p-esimo in x (il p-esimo bit è incluso ed i bit si contano a partire da zero, da destra verso sinistra).

    𝐀𝐋 𝐃𝐈 𝐋𝐀' 𝐃𝐄𝐋𝐋'𝐀𝐒𝐏𝐄𝐓𝐓𝐎 𝐓𝐄𝐂𝐍𝐈𝐂𝐎: Premetto che per far rientrare nell'immagine (click per ingrandire) tutto il numero ho cambiato, prendendo 

    x = 1110100011010101

    Che è composto da 16 bit, senza nessuna ragione precisa. Come vedi p è la posizione del bit da cui parti a leggere la sequenza, ed n è la larghezza della finestra: il codice ti permette di ottenere n bit a partire dal p-esimo scorrendo da sinistra verso destra (implicitamente p > n o p = n). 

    Giustamente potrebbe venirti il dubbio su quale possa essere una possibile applicazione di una simile supercazzola che sembra scritta per creare grattacapi agli studenti? Beh in effetti forse è solo un esercizio didattico, ma mi è venuta in mente una applicazione: il calcolo del resto nella divisione di un numero x per una qualche potenza del 2. Premetto qui che se sono in base decimale e prendo un certo numero, come x =  59615, e considero la sua divisione per 10 il resto della divisione è 5; se considero il resto della divisione di x per 10² (i.e. 100) questo sarà 15; se considero il resto della divisione di x per 10³ (i.e. 1000) ottengo 605 e più in generale se considero il resto della divisione per 10ᴺ ottengo le prime N cifre decimali del numero. Allo stesso modo se considero un numero x espresso in base di numerazione binaria e divido esso per 2ᴺ il resto di tale divisione sarà dato dalle prime N cifre binarie del numero. Così se leggi x ed N da tastiera puoi calcolare x % 2ᴺ scegliendo bit di partenza p = N-1 (perché i bit si contano da 0 e quindi l' N-esimo bit si trova in posizione N-1, ad esempio il 4° bit è nella posizione 3) ed ampiezza della finestra n = N, estrai esattamente il resto della divisione. 

    Il codice che implementa il mio esempio con quella procedura: https://pastebin.com/56S6hmzU

    𝐏𝐄𝐑𝐂𝐇𝐄' 𝐓𝐔𝐓𝐓𝐄 𝐐𝐔𝐄𝐒𝐓𝐄 𝐎𝐏𝐄𝐑𝐀𝐙𝐈𝐎𝐍𝐈: In generale saprai da quanto studiato tra i banchi di scuola che per convertire tutto un numero in binario si procede dividendo per 2 il numero da convertire finché non arrivi ad 1 salvandoti i vari resti delle divisioni, ed il numero di divisioni che devi svolgere sarà ⌈ log₂( x ) ⌉ perché questo è il numero di bit che devi ottenere (⌈ ⌉ rappresenta il più grande intero superiore o uguale al proprio argomento, se esso non è un intero, altrimenti non ha effetto ed il risultato è l'argomento stesso) e quindi ti servirebbero tante più operazioni quanto più il numero da convertire è grande; in generale se vorresti estrarre un sottogruppo di bit dalla codifica binaria di un numero dovresti prima convertirlo tutto facendo questo numero di operazioni. Invece il codice che hai proposto ti permette di ottenere lo stesso risultato facendo lo stesso numero di operazioni indipendentemente da quanto è grande x risparmiando potenzialmente molto tempo. È poi ben noto che le operazioni logiche che lavorano sui bit sono generalmente più veloci di quelle aritmetiche, quindi direi che lo scopo di un simile approccio è quello di ottimizzare le prestazioni. 

    Attachment image
Altre domande? Fai una domanda e ottieni le risposte che cerchi.