DOMANDA C++| manipolazione di bits

Marcus Aseth

Utente Attivo
404
138
OS
Windows 10
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"

C:
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:
 
Ultima modifica:
  • Mi piace
Reazioni: VidRam

signore del tempo

Utente Èlite
3,228
491
CPU
Intel Core i5 4670K
Scheda Madre
Asus Z87-Plus
HDD
WD Caviar Green 500GB
RAM
G.Skill Ares 2x4GB 1600MHz
GPU
Sapphire 7850 1GB @ 1050MHz
Audio
Integrata
Monitor
Acer V193w
PSU
XFX ProSeries 550W Core Edition
Case
CM HAF 912 plus
OS
ArchLinux + KDE - Windows 10
L'accesso è ristretto a registrati, puoi postare la traccia?
 
  • Mi piace
Reazioni: Marcus Aseth

Marcus Aseth

Utente Attivo
404
138
OS
Windows 10
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

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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:
Codice:
#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.
 
Ultima modifica:
  • Mi piace
Reazioni: Marcus Aseth

Marcus Aseth

Utente Attivo
404
138
OS
Windows 10
@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

Utente Attivo
609
222
CPU
i5 6600k
Dissipatore
AIO H100
Scheda Madre
ASUS z170 Deluxe
HDD
1 WD Blue 1 TB; evo 850 500gb
RAM
Vengeance 4x4
GPU
GTX 1070ti MSI
Audio
Nope
Monitor
MG278Q
Case
750D Corsair
Net
Fastweb 200/30
OS
PucyBuntu
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:


C:
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

Utente Attivo
404
138
OS
Windows 10
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:
C++:
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

Utente Attivo
609
222
CPU
i5 6600k
Dissipatore
AIO H100
Scheda Madre
ASUS z170 Deluxe
HDD
1 WD Blue 1 TB; evo 850 500gb
RAM
Vengeance 4x4
GPU
GTX 1070ti MSI
Audio
Nope
Monitor
MG278Q
Case
750D Corsair
Net
Fastweb 200/30
OS
PucyBuntu
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:
C++:
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/
 
  • Mi piace
Reazioni: Marcus Aseth

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!