DOMANDA C++| manipolazione di bits

[Marcus Aseth]

Salve gente, provavo a risolvere questa sfida qua in C++, quella sotto è la mia soluzione (corretta), ma visto che non sono tanto pratico di "bitwise operations", giusto per curiosità mi domandavo se c'era qualche punto dove potevo ottimizzare il codice in maniera ovvia :P

input string:

"128.42.5.4/21"

std::string calculateNetworkAddress(std::string cidr) {

    //build networkMask
    int maskVal = stoi(string(cidr.begin() + cidr.find('/') + 1,
                              cidr.end()));
    uint32_t networkMask{};
    for (int i = 31; i > 31 - maskVal; i--) {
        networkMask |= 1 << i;
    }

    //extract IP digits
    vector<uint8_t> IP;
    auto begin = cidr.begin(), end = cidr.begin();
    while (end != cidr.end())
    {
        if (!isdigit(*end)) {
            int n = stoi(string(begin, end));
            IP.push_back(n);
            begin = end + 1;
        }
        end++;
    }
 
    //add together the bits of the 4 bytes representing the IP
    uint32_t networkAddressVal{};
    for (size_t i = 0; i < 4; i++){
        networkAddressVal |= IP[i] << (3 - i)*8;
    }
    //[Logical AND]  between IP bits and mask bits
    networkAddressVal &= networkMask;

    //extract new ip number from networkAddress bits
    string result;
    for (size_t i = 0; i < 4; i++) {
        uint8_t val = {};
        val |= networkAddressVal >> 8*(3-i);
        result += to_string(val);
        if (i < 3) { result += '.'; }
    }
    return result;
}

output string:

"128.42.0.0"

 

[signore del tempo]

L'accesso è ristretto a registrati, puoi postare la traccia?

 

[Marcus Aseth]

Ah, non avevo idea.
Ecco:

Given an IP address in CIDR notation. Calculate it's network address.

Example
For cidr = "128.42.5.4/21", the output should be
calculateNetworkAddress(cidr) = "128.42.0.0".
The network address is the logical AND of the respective bits in the binary representation of the IP address and network mask.

128.42.5.4 in binary: 10000000 00101010 00000101 00000100
network mask in binary: 11111111 11111111 11111000 00000000
-----------------------------------------------------------
[Logical AND] 10000000 00101010 00000000 00000000

Finally convert these four blocks to decimal to get the network address.
Thus the network address is calculated as "128.42.0.0" for the CIDR "128.42.5.4/21".

Input/Output

• [time limit] 500ms (cpp)

• [input] string cidr
  
  The string in the format "n1.n2.n3.n4/m", where all n-s are 0 ≤ n ≤ 255 and 0 ≤ m ≤ 32.
  
  Guaranteed constraints:
  9 ≤ cidr.length < 20.
  
  
• [output] string
  
  The network address of the given CIDR notation.

 

[DispatchCode]

Il mio C++ è molto arrugginito, ho quindi riciclato parti del tuo codice @Marcus Aseth , per non dover scrivere senza funzioni built-in delle parti (come splittare una stringa...).

Comunque molte cose sono semplificabili. Ti mostro una delle altre possibili soluzioni:

#include <iostream>
#include <sstream>
#include <string>
#include <climits>

uint32_t networkMask(std::string cidr)
{
    int maskVal = 32 - stoi(std::string(cidr.begin() + cidr.find('/') + 1,
                              cidr.end()));

    return ULONG_MAX << maskVal;
}

std::string networkAddress(std::string cidr)
{
    uint32_t mask  = networkMask(cidr);
    std::string ip = cidr.substr(0,cidr.find("/"));
 
    uint32_t ip_n = 0;
 
    auto begin = ip.begin(), end = ip.begin();
    while (end != ip.end())
    {
        if (!isdigit(*end))
        {
            int n = stoi(std::string(begin, end));
        
            ip_n = (ip_n | n) << 8;
        
            begin = end + 1;
        }
        end++;
    }
 
    ip_n &= mask;
 
    std::string out_addr;
    out_addr += std::to_string(ip_n >> 24 & 0xFF) + ".";
    out_addr += std::to_string(ip_n >> 16 & 0xFF) + ".";
    out_addr += std::to_string(ip_n >> 8 & 0xFF)  + ".";
    out_addr += std::to_string(ip_n & 0xFF);

    return out_addr;
}


int main()
{
    std::string cidr = "128.42.5.4/21";
    std::string netAddr = networkAddress(cidr);
 
    std::cout << netAddr;
 
    return 0;
}

Per la maschera: se conosci quanti bit sono settati a 1 (/21 in quel caso), sai quanti sono a 0 (32-21). Quindi prendendo il valore massimo esprimibile con un uint32 (quindi tutti i bit a 1) sai di quanti bit shiftare a sinistra (32-21 = 11); ogni bit shiftato provoca la comparsa di uno 0 a destra.

Per quanto riguarda l'applicazione della maschera: ciò che ti è sufficiente fare è trasformare ogni byte in decimale (quindi l'unica rogna è lo split) e fare un OR per ottenere un unico numerone a 32bit. Fatto ciò prendi il numero nel suo insieme ed applichi la maschera calcolata in precedenza usando un AND.
Poi ti è sufficiente ottenere i singoli byte e dividerli da un punto.
Nel mio caso evito il for e la moltiplicazione per ottenere poi i singoli byte concatenando ed shiftando di un numero di bit differente (non è escluso che il compilatore anche nel tuo caso alla fine faccia qualcosa di analogo).
Posto che potresti fare: i << 3 al posto di i*8, ed evitare di moltiplicare anche tu.

Una soluzione più rapida è applicare il byte della maschera al byte del numero che stai leggendo e poi comporre direttamente la stringa di output.

 

[Marcus Aseth]

@DispatchCode grazie della spiegazione (almeno 4 trucchi ai quali non ho pensato), terrò a mente per la prossima sfida simile a questa, sopra tutto " return ULONG_MAX << maskVal;", nice one :D

 

[Hobet]

Salve gente, provavo a risolvere questa sfida qua in C++, quella sotto è la mia soluzione (corretta), ma visto che non sono tanto pratico di "bitwise operations", giusto per curiosità mi domandavo se c'era qualche punto dove potevo ottimizzare il codice in maniera ovvia :P

input string:

std::string calculateNetworkAddress(std::string cidr) {

    //build networkMask
    int maskVal = stoi(string(cidr.begin() + cidr.find('/') + 1,
                              cidr.end()));
    uint32_t networkMask{};
    for (int i = 31; i > 31 - maskVal; i--) {
        networkMask |= 1 << i;
    }

    //extract IP digits
    vector<uint8_t> IP;
    auto begin = cidr.begin(), end = cidr.begin();
    while (end != cidr.end())
    {
        if (!isdigit(*end)) {
            int n = stoi(string(begin, end));
            IP.push_back(n);
            begin = end + 1;
        }
        end++;
    }
 
    //add together the bits of the 4 bytes representing the IP
    uint32_t networkAddressVal{};
    for (size_t i = 0; i < 4; i++){
        networkAddressVal |= IP[i] << (3 - i)*8;
    }
    //[Logical AND]  between IP bits and mask bits
    networkAddressVal &= networkMask;

    //extract new ip number from networkAddress bits
    string result;
    for (size_t i = 0; i < 4; i++) {
        uint8_t val = {};
        val |= networkAddressVal >> 8*(3-i);
        result += to_string(val);
        if (i < 3) { result += '.'; }
    }
    return result;
}

output string:

Se vuoi ulteriormente migliorarlo, ti consiglio di evitare di usare le librerie esterne, il succo di questi esercizi è questo. Cerca di lavorare sul char crudo.

 

[Marcus Aseth]

Forse è quello, visto che nella classifica i posti più alti sono assegnati a chi usa il minor numero di char, ho persino visto uno che lo ha risolto in 2-3 righe scrivendo sta roba qua:

int a,t;
string S, calculateNetworkAddress(auto s) {
    for (int c : s+"       ")
        t=c<33?a&=-1<<-t,S="."+c%2+to_string(a&255) + S, a >>= 8,0:c<48?a=a<<8|t,0:10*t+c%12;

    return S;
}

Ma onestamente, lo trovo sia orribile da vedere che assolutamente non chiaro per chiunque dovesse leggere un codice simile senza averci perso tempo sopra a ragionare su cosa quel codice fà, quindi preferisco imparare a scrivere codice magari meno performante ma che quando uno lo vede capisce al volo cosa sta succedendo :)

 

[Hobet]

Forse è quello, visto che nella classifica i posti più alti sono assegnati a chi usa il minor numero di char, ho persino visto uno che lo ha risolto in 2-3 righe scrivendo sta roba qua:

int a,t;
string S, calculateNetworkAddress(auto s) {
    for (int c : s+"       ")
        t=c<33?a&=-1<<-t,S="."+c%2+to_string(a&255) + S, a >>= 8,0:c<48?a=a<<8|t,0:10*t+c%12;

    return S;
}

Ma onestamente, lo trovo sia orribile da vedere che assolutamente non chiaro per chiunque dovesse leggere un codice simile senza averci perso tempo sopra a ragionare su cosa quel codice fà, quindi preferisco imparare a scrivere codice magari meno performante ma che quando uno lo vede capisce al volo cosa sta succedendo :)

Ed hai perfettamente ragione, infatti non ti verrò mai chiesto di reinventare la ruota, ma di sicuro ti chiederanno come funziona e se non lo sai avrai dei brutti quarti d'ora ai colloqui o con i colleghi tua a lavoro.

Ti consiglio di leggere questo articolo che a mio parere esprime esattamente quello che io voglio dire:

https://blog.codinghorror.com/why-cant-programmers-program/