Spiegazione da decimale a binaria

1
string convertDigitsToBinary(int n) {
        string ans;
        if (n == 0) return "0";

        while (n > 0) {
        int rem = n % 2; 
        ans.push_back((char)('0' + rem));
        n /= 2;
        }

        reverse(ans.begin(), ans.end());
        return ans;
}

Capisco come funziona l'algoritmo per% il numero per 2 e poi uso il resto per creare la rappresentazione binaria, non so come funziona.

Credo di non vedere la connessione usando il resto per determinare se i bit sono 0 o 1

Quindi nel codice sopra: N = 6 sarebbe 110

    
posta abcf 21.11.2016 - 02:53
fonte

2 risposte

4

Il resto è il modo eccessivo di testare il bit più basso. Se ci pensi, qualsiasi valore% 2 produrrà solo 0 o 1, il che accade corrisponde al valore del bit più basso.

Un modo di pensare più matematico o alternativo è anche o dispari , che può anche essere ottenuto da% con 2. Se il valore è pari ,% di 2 produce zero. E se il valore è pari, significa che il bit più basso è zero, quindi% di 2 che produce zero significa che il bit più basso è zero.

Il bit più basso in binario rappresenta 2 0 . Le altre posizioni in ordine crescente rappresentano 2 1 e oltre. L'unico modo per creare un numero dispari in binario è aggiungere 2 0 = 1, operazione che viene eseguita impostando il bit più basso. (Nota: questo si applica anche ai numeri negativi purché siano memorizzati in modulo di complemento 2 come fanno tutti i computer moderni) .

Ri: l'overkill, nella maggior parte delle lingue puoi fare una maschera più semplice con costante 1, come n & 1 , che è un modo più diretto di controllare il valore del bit più basso. Dividi per 2 è il modo matematico di spostare i bit di una posizione a destra; come nel mascheramento, la maggior parte delle lingue ha il modo più diretto di spostarsi, ad es. n >>= 1; Questi sono spesso preferiti perché hanno meno problemi, come le stranezze nel gestire mod e la divisione degli interi negativi (la divisione computer, specialmente con gli interi, differisce in modo sottile dalla divisione matematica, che risulterebbe in frazioni o real). Inoltre, specialmente sui processori più vecchi, il modo più semplice era più veloce, essendo fattibile con una logica semplice invece di un divisore che è piuttosto complesso.

    
risposta data 21.11.2016 - 03:20
fonte
2

L'algoritmo generale per la formattazione di un intero positivo come stringa in qualsiasi base è:

  1. inizia con una stringa vuota s e un numero intero di lavoro n
  2. aggiungi la cifra inferiore (meno significativa) di n nella base desiderata a s
  3. divide n dalla base (truncate to integer)
  4. ripeti da 2 fino a n è zero

I guess I don't see the connection in using the remainder to determine whether the bits are 0 or 1

Ma la cifra meno significativa di n nella base b è definita come n % b . Provalo nella base 10 se ti aiuta a confermare la tua intuizione, ma la base 2 non è diversa.

Come per

Remainder is the overkill way of testing the lowest bit

remainder (modulo) è il modo canonico per farlo. L'uso di bitwise & è invece un'ottimizzazione per basi che sono potenze di due.

    
risposta data 21.11.2016 - 15:20
fonte

Leggi altre domande sui tag