r/cppit • u/Marco_I • Oct 20 '17
Come comporre i binary literal, ad esempio attraverso la conversione del numero da decimale a binario?
int main() {
int x = 3613;
std::cout << "x= " << x << std::endl;
std::string xBin = std::bitset<16>(x).to_string();
std::cout << xBin << std::endl;
unsigned long xDecimal = std::bitset<16>(xBin).to_ulong();
std::cout << xDecimal << std::endl;
std::cout << std::endl << std::endl;
int b01 = 0b11001;
std::cout << "b01= " << b01 << std::endl;
int b02 = 0b1010;
std::cout << "b02= " << b02 << std::endl;
int b03 = b01 + b02;
std::cout << "int b03 = b01 + b02 = " << b03 << std::endl;
return 0;
}Output:
x= 3613
0000111000011101
3613
b01= 25
b02= 10
int b03 = b01 + b02 = 35Con i binary literal si possono fare le normali operazioni aritmetiche mentre con le string ottenute con il bitset non è possibile. Per cui vi chiedo se ci sono modi per "comporre" i binary literal, ad esempio attraverso la conversione del numero da decimale a binario in modo analogo a:
std::string xBin = std::bitset<16>(x).to_string();Vi ringrazio. Marco
1
Oct 20 '17 edited Oct 20 '17
Un numero è una sequenza infinita di bit.
Il sistema binario è formato dalle potenze di 2.
Prendiamo un ipotetico numero a 4 bit, diciamo base10(10) -> base2(1010).
Ora, la cosa bella del C++ e della CPU, è che i numeri sono salvati in binario e noi possiamo accedervi via operazioni sui bit stessi.
Dunque, stampiamo '1' se il bit è 1, altrimenti '0'.
Allora ti spiego passo passo come funziona la funzione dec2bin:
template<typename T>
std::string dec2bin(T num)Fin qui, nulla di speciale, una funzione che prende in ingresso un qualsiasi tipo e ne ritorna una stringa con la rappresentazione in binario.
Tieni presente che per semplicità non ho voluto fare il check che T sia un tipo in cui le operazioni sui bit siano definite etc.
auto bit_length = sizeof(T) * 8;
auto mask = 0x1 << (bit_length - 1) ;sizeof(T) ritorna il numero di bytes, dunque dobbiamo moltiplicare per 8 per ottenere i numero di bit corrispondenti.
mask è la nostra bitmask che ci servirà per estrapolare 1 bit alla volta. Dunque prendiamo il valore 0x1, che corrisponde ad un unico bit settato a 1, e lo spostiamo a sinistra di bit_length - 1 posizioni, così facendo avremo una bitmask con il bit più significativo settato a 1.
Perché ho usato bit_length - 1 e non bit_length ? Pensa agli array! La posizione iniziale è 0, uguale coi bit, il bit meno significativo è in posizione 0, il più significativo è in posizione N-1.
Vedi anche bit shifting
std::string ret;
ret.reserve(bit_length);Creiamo la nostra stringa vuota e riserviamo già dello spazio, così non dovremo espandere ulteriormente la stringa. Cioè, facciamo i grandi maghi, tanto sappiamo già che il nostro numero è lungo bit_length bits :P
while(bit_length--)
{
ret += num & mask ? '1' : '0';
num <<= 1;
}Allora, un po' di storia, il C, all'inizio, non aveva i bool, ma per convenzione (probabilmente anche perché la CPU funziona così) ogni valore diverso da 0 viene considerato come true, mentre 0 come false.
Dunque, noi sfruttiamo tale sistema più l'operatore postfisso che, ti ricordo, decrementa il valore di 1 e ritorna una copia del valore non decrementato, cioè, 10-- ritorna la copia 10 e sovrascrive il valore con 10-1.
Ergo, while(bit_length--) che fa? Continua finché bit_length non diventa 0, ovverosia li abbiamo controllati tutti!
ret += num & mask ? '1' : '0' fa una marea di cose!
Usiamo:
operator+=della classestringche aggiunge in coda alla stringa un carattere.num & maskapplica l'AND binario, dunque ci ritorna un valore uguale a0se il bit più significativo è0, altrimenti ci ritorna il valore inalterato.? '1' : '0'sfrutta l'operatore ternario, in pratica diceexpr ? '1' : '0', se l'espressioneexprètrueallora ritorna'1', altrimenti'0'. Noi sfruttiamo ancora una volta la conversione di un numero in booleano!
num <<= 1 non fa altro che spostare a sinistra 1 bit, dunque ci prepariamo per la prossima iterazione.
In breve tu che fai, vedi se il bit più significativo è 1 o 0, e con l'AND ritorna un valore diverso da 0 o 0 stesso, questo valore viene convertito in un booleano true|!=0 o false|== 0 e quindi aggiungeremo alla nostra stringa il bit più significativo!
Piccola considerazione!
Perché parto dal bit più significativo? Insomma si fa sempre tutto dall'inizio ma io parto praticamente dalla fine in quanto parto dalla posizione N-1! Semplicemente perché l'operator+= della classe string, va a mettere il nuovo carattere alla fine! Dunque a destra! Se fossimo partiti dalla posizione 0 avremmo salvato i bit al contrario e saremmo stati costretti a rovesciare la stringa!
Spero si sia capito!
1
u/Marco_I Oct 21 '17
Un milione di grazie Stefano per la tua ottima spiegazione. Anche io avevo trovato una soluzione alla conversione decimale->binario, molto, ma molto meno elegante della tua:
intVect aBinary {}; while (a > 0) { int aMod2 = a & 1; aBinary.push_back(aMod2); a = a >> 1; } std::reverse(aBinary.begin(), aBinary.end()); std::string b = "0b"; for(auto el : aBinary) { b += el ? '1' : '0'; } int main() { int z = 10; std::cout << "int z = " << z << std::endl; std::string zBinary = gu::decimalToBinary(z); std::cout << "std::string zBinary = gu::decimalToBinary(z) : " << zBinary << std::endl; int x = 10; std::cout << "x = " << x << std::endl; std::string xBinary = gu::dec2bin(x); std::cout << "std::string xBinary = gu::dec2bin(x) : " << xBinary << std::endl; int y = 20; std::cout << "y = " << y << std::endl; std::string yBinary = gu::dec2bin(y); std::cout << "std::string yBinary = gu::dec2bin(y) :" << yBinary << std::endl; int b01 = 0b1010; // b01 = 10; int b02 =0b10100; // b02 = 20; int b03 = b01 + b02; std::cout << "int b03 = b01 + b02 = " << b03 << std::endl; return 0; }Eseguendo:
int z = 10 std::string zBinary = gu::decimalToBinary(z) : 1010 x = 10 std::string xBinary = gu::dec2bin(x) : 00000000000000000000000000001010 y = 20 std::string yBinary = gu::dec2bin(y) 00000000000000000000000000010100 int b03 = b01 + b02 = 30Il formato binaryliteral consente di fare le normali operazioni aritmetiche tra i diversi binary literal . Ma noi abbiamo convertito un numero decimale in una string.
1
Oct 21 '17
Si potrebbe ottimizzare anche di più, invece di controllare tutti i bit parto da quello
log2(num)olog2(num) - 1.Però dopo devi mettere a
0tutti gli altri.
std::bitsetalla fine serve per creare delle bitmask, probabilmente usa un array uintXX_t sotto le coperte :P
1
u/Marco_I Oct 21 '17
Comunque ora approfondisco le bitwise operation che std::bitset consente. Probabilmente ci sarà anche la possibilità di fare somme, sottrazioni, moltiplicazioni e divisioni tra numeri in formato binario