C Vorstellungsgespräch – Casting und Vergleich

Lesezeit: 10 Minuten

Benutzeravatar von Itzik984
Itzik984

Ich wurde mit einer kniffligen (IMO) Frage konfrontiert. Ich musste zwei vergleichen MAC-Adressenauf die effizienteste Weise.

Der einzige Gedanke, der mir in diesem Moment durch den Kopf ging, war die triviale Lösung – a for Schleife und Orte vergleichen, und das tat ich, aber der Interviewer zielte auf ein Casting ab.

Die MAC-Definition:

typedef struct macA {
   char data[6];
} MAC;

Und die Funktion ist (die, die ich implementieren sollte):

int isEqual(MAC* addr1, MAC* addr2)
{
    int i;

    for(i = 0; i<6; i++)
    {
        if(addr1->data[i] != addr2->data[i]) 
            return 0;
    }
    return 1;
}

Aber wie erwähnt, zielte er auf das Casting ab.

Das heißt, um die gegebene MAC-Adresse irgendwie in ein Int umzuwandeln, beide Adressen zu vergleichen und zurückzukehren.

Aber beim Gießen int int_addr1 = (int)addr1;, werden nur vier Bytes gecastet, richtig? Soll ich die restlichen überprüfen? Bedeutet die Standorte 4 und 5?

Beide char und int sind Integer-Typen, also ist Casting legal, aber was passiert in der beschriebenen Situation?

  • Entschuldigung, aber wer hat gesagt, dass Sie irgendein Int-Casting machen müssen? er wollte, dass du Zeichenvergleiche durchführst

    – Noam Rathaus

    31. Dezember 2013 um 14:46 Uhr

  • Ist dies für ein eingebettetes System gedacht?

    – Michael Hampton

    31. Dezember 2013 um 18:25 Uhr

  • Da die Größe eines MAC per Definition 48 Bit (6 Byte) beträgt, ist es sinnvoll, #define MAC_SIZE (6) zu verwenden.

    – ChuckCottrill

    31. Dezember 2013 um 18:58 Uhr

  • Für was es wert ist, wenn ich diese Art von Frage stelle – was ich versuche nicht zu tun! — Ich suche im Allgemeinen nicht nach einer einzigen Antwort, sondern danach, welche Fragen der Bewerber zu den Einschränkungen und Prioritäten stellt und ob er diskutieren kann, warum er sich für eine Antwort und nicht für eine andere entschieden hat.

    – Keschlam

    1. Januar 2014 um 5:20 Uhr

Wenn er mit diesem Ansatz wirklich unzufrieden ist (was im Wesentlichen ein Hirnfurz ist, da Sie nicht Megabytes oder Gigabytes an Daten vergleichen, muss man sich in diesem Fall also keine Gedanken über “Effizienz” und “Geschwindigkeit” machen), nur sagen Sie ihm, dass Sie der Qualität und Geschwindigkeit der Standardbibliothek vertrauen:

int isEqual(MAC* addr1, MAC* addr2)
{
    return memcmp(&addr1->data, &addr2->data, sizeof(addr1->data)) == 0;
}

  • @H2CO3, Sie können einen Beitrag schreiben, der ein Betriebssystem-E / A-Subsystem umschreibt, und 35 Punkte sammeln. Schlagen Sie einen Interviewer nieder – ein Vorgang, den jeder von Natur aus hasst – und 150!

    – Ente

    31. Dezember 2013 um 15:00 Uhr

  • @ H2CO3: Das stimmt zwar data ist ein Array und kein Zeiger, memcmp(addr1->data, addr2->data, sizeof(addr1->data)) ist immer noch richtig (aufgrund von Zerfall), nein?

    – legends2k

    31. Dezember 2013 um 15:06 Uhr

  • @hackks: Für mich stellen die Adler nur dar, dass “Sie sich jederzeit anmelden können, aber Sie können sich niemals abmelden” …

    – Kerrek SB

    31. Dezember 2013 um 15:17 Uhr

  • @chux Weil am Ende der Struktur möglicherweise ein Füllzeichen vorhanden ist, das nicht angegebene Füllbytes enthält. Das würde zu falsch negativen Ergebnissen führen.

    Benutzer529758

    31. Dezember 2013 um 21:32 Uhr

  • @Lee Was? “memcmp von zwei Ints ist ineffizient” ist nicht so wie es ist (siehe die Diskussion oben). Außerdem “sane code” == Code, der nicht unnötig “clever” ist und sich nicht auf UB verlässt, wenn er nicht benötigt wird. Eine Eigenschaft von vernünftigem Code ist die Abhängigkeit von der Standardbibliothek. Du siehst jetzt?

    Benutzer529758

    31. Dezember 2013 um 23:55 Uhr


Benutzeravatar von Kerrek SB
Kerrek SB

Wenn Ihr Gesprächspartner verlangt, dass Sie undefiniertes Verhalten zeigen, würde ich wahrscheinlich woanders nach einem Job suchen.

Der richtige anfängliche Ansatz wäre, die MAC-Adresse in etwas wie a zu speichern uint64_t, zumindest im Speicher. Dann wären Vergleiche trivial und effizient umsetzbar.

  • @ ltzik984 Nein, höchstwahrscheinlich hat er keine Ahnung, dass dies ein undefiniertes Verhalten ist.

    Benutzer529758

    31. Dezember 2013 um 14:43 Uhr

  • @Abyx: Warum nicht als Antwort posten, was Ihrer Meinung nach getan werden sollte, und wir können sehen, ob es UB ist?

    – Kerrek SB

    31. Dezember 2013 um 14:55 Uhr

  • @Abyx Es führt zu UB. Genau in dem Moment, in dem Sie den Zeiger auf einen inkompatiblen Typ dereferenzieren.

    Benutzer529758

    31. Dezember 2013 um 14:59 Uhr

  • @Abyx: Sie kennen C nicht, aber Sie stimmen mich ab, weil ich nichts vorgeschlagen habe, was falsch wäre? :-S

    – Kerrek SB

    31. Dezember 2013 um 15:14 Uhr

  • @rm5248: Eine MAC-Adresse ist nur eine Zahl. Es ist, als ob Sie darauf bestanden hätten, Ihre eigene 21-Bit-Ganzzahl für Textzeichen zu entwerfen, anstatt die Vernünftigen zu verwenden char32_t.

    – Kerrek SB

    31. Dezember 2013 um 23:15 Uhr

Benutzeravatar von Glenn Teitelbaum
Glenn Teitelbaum

Cowboyzeit:

typedef struct macA {
   char data[6];
} MAC;

typedef struct sometimes_works {
   long some;
   short more;
} cast_it

typedef union cowboy
{
    MAC real;
    cast_it hack;
} cowboy_cast;

int isEqual(MAC* addr1, MAC* addr2)
{
     assert(sizeof(MAC) == sizeof(cowboy_cast));  // Can't be bigger
     assert(sizeof(MAC) == sizeof(cast_it));      // Can't be smaller

     if ( ( ((cowboy_cast *)addr1)->hack.some == ((cowboy_cast *)addr2)->hack.some )
       && ( ((cowboy_cast *)addr1)->hack.more == ((cowboy_cast *)addr2)->hack.more ) )
             return (0 == 0);

     return (0 == 42);
}

  • Ich bin mir nicht sicher, wie Sie hier mit der Gewerkschaft viel gewinnen. Ich meine, wenn Sie Ausrichtungsprobleme mit Ihrem MAC haben, werden Sie sie immer noch haben. Wenn Sie keine Ausrichtungsprobleme haben, verlassen Sie sich immer noch darauf, dass die Größe von (MAC) 6 ist und / oder die Polsterung an der richtigen Stelle ist. Es scheint, als ob Sie die gleichen Risiken eingehen, wenn Sie den MAC/Datenpunkt direkt übertragen.

    – Richard Plunkett

    31. Dezember 2013 um 17:02 Uhr

  • @RichardPlunkett Ich habe die Cowboy-Besetzung aufgenommen, weil sie manchmal in Interviews oder Legacy-Code auftaucht und ob sie Vorteile gegenüber der direkten Besetzung hat oder memcmp ist nicht so wichtig, wie diesen Ansatz zu kennen und höchstwahrscheinlich zu vermeiden. Aber wer es nicht gesehen hat, kann nicht sagen warum.

    – Glenn Teitelbaum

    31. Dezember 2013 um 17:08 Uhr


  • @RichardPlunkett Nein. Gewerkschaften garantieren eine korrekte Ausrichtung. Seit C99 ist Union-basiertes Typpunning legal (es ist nicht mehr UB), im Gegensatz zu Aliasing durch Zeiger auf inkompatible Typen.

    Benutzer529758

    31. Dezember 2013 um 21:34 Uhr

  • Sollte das nicht sein typedef struct sometimes_works { uint32_t some; uint16_t more; } cast_it; für Portabilität?

    – Tomlogik

    1. Januar 2014 um 1:11 Uhr

  • @H2CO3, ich glaube nicht, dass eine Gewerkschaft hier die Ausrichtung garantiert. Ich meine, wenn Sie eine cowboy_cast-Variable deklarieren, wird sie dafür korrekt ausgerichtet, aber Sie können nicht garantieren, dass verschiedene MAC-Strukturen die richtige Ausrichtung für einen cowboy_cast haben, und wir erhalten einen MAC-Zeiger.

    – Richard Plunkett

    1. Januar 2014 um 1:47 Uhr

Benutzeravatar von Aprori
Apriori

An einer effizienten Implementierung ist nichts auszusetzen, denn soweit Sie wissen, wurde festgestellt, dass es sich um heißen Code handelt, der viele Male aufgerufen wird. Und auf jeden Fall ist es in Ordnung, wenn Interviewfragen seltsame Einschränkungen haben.

Logisches UND ist aufgrund der Kurzschlussauswertung a priori eine Verzweigungsanweisung, auch wenn es nicht auf diese Weise kompiliert wird, also vermeiden wir es, wir brauchen es nicht. Wir müssen unseren Rückgabewert auch nicht in einen wahren bool (Stimmt oder FALSCHnicht 0 oder alles, was nicht null ist).

Hier ist eine schnelle Lösung für 32-Bit: XOR erfasst die Unterschiede, OR zeichnet den Unterschied in beiden Teilen auf und NOT negiert die Bedingung in GLEICH, nicht UNGLEICH. Die LHS und RHS sind unabhängige Berechnungen, sodass ein superskalarer Prozessor dies parallel ausführen kann.

int isEqual(MAC* addr1, MAC* addr2)
{
    return ~((*(int*)addr2 ^ *(int*)addr1) | (int)(((short*)addr2)[2] ^ ((short*)addr1)[2]));
}

BEARBEITEN

Der Zweck des obigen Codes bestand darin zu zeigen, dass dies ohne Verzweigung effizient durchgeführt werden kann. Kommentare haben darauf hingewiesen, dass C++ dies als undefiniertes Verhalten klassifiziert. Obwohl dies wahr ist, handhabt VS dies gut. Ohne die Strukturdefinition und Funktionssignatur des Interviewers zu ändern, muss eine zusätzliche Kopie erstellt werden, um undefiniertes Verhalten zu vermeiden. Der nicht undefinierte Verhaltensweg ohne Verzweigung, aber mit einer zusätzlichen Kopie wäre also wie folgt:

int isEqual(MAC* addr1, MAC* addr2)
{
    struct IntShort
    {
        int   i;
        short s;
    };

    union MACU
    {
        MAC addr;
        IntShort is;
    };

    MACU u1;
    MACU u2;

    u1.addr = *addr1; // extra copy
    u2.addr = *addr2; // extra copy

    return ~((u1.is.i ^ u2.is.i) | (int)(u1.is.s ^ u2.is.s)); // still no branching
}

Benutzeravatar von RichardPlunkett
Richard Plunkett

Dies würde auf den meisten Systemen funktionieren und schneller sein als Ihre Lösung.

int isEqual(MAC* addr1, MAC* addr2)
{
    return ((int32*)addr1)[0] == ((int32*)addr2)[0] &&  ((int16*)addr1)[2] == ((int16*)addr2)[2];
}

wäre auch gut inline, könnte in der Mitte der Schleife auf einem System praktisch sein, wo Sie überprüfen können, ob die Details realisierbar sind.

  • Und so erhebt die Hydra des Undefinierten Verhaltens mehrere ihrer vielen Köpfe.

    – Kerrek SB

    31. Dezember 2013 um 15:01 Uhr

  • Obwohl dies zutrifft, wäre es erwähnenswert, dass dies auf undefiniertem Verhalten beruht.

    Benutzer529758

    31. Dezember 2013 um 15:01 Uhr


  • Definieren Sie die Struktur zumindest als Union mit uint16_t neu[3] oder uint32_t+uint16_t, wenn zusätzliches Auffüllen zulässig ist, und vergleichen Sie diese Felder, um UB zu vermeiden. Natürlich sind viele Compiler schlau genug, memcmp() mit fester Größe entsprechend zu optimieren, besonders wenn sie einen Ausrichtungshinweis erhalten

    – doynax

    31. Dezember 2013 um 15:06 Uhr

  • Das int16 Der Vergleich sollte auf dem dritten Element (Index 2) erfolgen, nicht auf dem zweiten.

    – Benjamin Lindley

    31. Dezember 2013 um 15:08 Uhr

  • @doynax: Das offensichtlichste Problem besteht darin, dass die Plattform möglicherweise einen ausgerichteten Speicher für Ganzzahloperationen benötigt. Wenn Ihr Zeichenzeiger dies nicht erfüllt, kann Ihre CPU eine Ausnahme auslösen. x86 hat dieses Problem nicht, aber es gibt andere Plattformen, die das tun.

    – Kerrek SB

    31. Dezember 2013 um 16:16 Uhr

chux – Stellt Monicas Benutzeravatar wieder her
Chux – Wiedereinsetzung von Monica

Nicht tragbare Gießlösung.

In einer Plattform, die ich verwende (PIC24-basiert), gibt es einen Typ int48also eine sichere Annahme char ist 8 Bit und die üblichen Ausrichtungsanforderungen:

int isEqual(MAC* addr1, MAC* addr2) {
  return *((int48_t*) &addr1->data) == *((int48_t*) &addr2->data);
}

Das ist natürlich auf vielen Plattformen nicht nutzbar, aber auch eine Reihe von Lösungen, die je nach Annahme nicht portabel sind int Größe, no paddingetc.

Die am besten tragbare Lösung (und bei einem guten Compiler einigermaßen schnell) ist die memcmp() angeboten von @H2CO3.

Gehen Sie zu einer höheren Designebene und verwenden Sie einen ausreichend breiten Integer-Typ wie uint64_t Anstatt von struct macAwie von Kerrek SB vorgeschlagen, ist sehr ansprechend.

  • Und so erhebt die Hydra des Undefinierten Verhaltens mehrere ihrer vielen Köpfe.

    – Kerrek SB

    31. Dezember 2013 um 15:01 Uhr

  • Obwohl dies zutrifft, wäre es erwähnenswert, dass dies auf undefiniertem Verhalten beruht.

    Benutzer529758

    31. Dezember 2013 um 15:01 Uhr


  • Definieren Sie die Struktur zumindest als Union mit uint16_t neu[3] oder uint32_t+uint16_t, wenn zusätzliches Auffüllen zulässig ist, und vergleichen Sie diese Felder, um UB zu vermeiden. Natürlich sind viele Compiler schlau genug, memcmp() mit fester Größe entsprechend zu optimieren, besonders wenn sie einen Ausrichtungshinweis erhalten

    – doynax

    31. Dezember 2013 um 15:06 Uhr

  • Das int16 Der Vergleich sollte auf dem dritten Element (Index 2) erfolgen, nicht auf dem zweiten.

    – Benjamin Lindley

    31. Dezember 2013 um 15:08 Uhr

  • @doynax: Das offensichtlichste Problem besteht darin, dass die Plattform möglicherweise einen ausgerichteten Speicher für Ganzzahloperationen benötigt. Wenn Ihr Zeichenzeiger dies nicht erfüllt, kann Ihre CPU eine Ausnahme auslösen. x86 hat dieses Problem nicht, aber es gibt andere Plattformen, die das tun.

    – Kerrek SB

    31. Dezember 2013 um 16:16 Uhr

Um Wortspiele korrekt auszuführen, müssen Sie eine Union verwenden. Andernfalls brechen Sie die strikten Aliasing-Regeln, denen bestimmte Compiler folgen, und das Ergebnis ist undefiniert.

int EqualMac( MAC* a , MAC* b )
{
    union
    {
        MAC m ;
        uint16_t w[3] ;

    } ua , ub ;

    ua.m = *a ;
    ub.m = *b ;

    if( ua.w[0] != ub.w[0] )  
        return 0 ;

    if( ua.w[1] != ub.w[1] )
        return 0 ;

    if( ua.w[2] != ub.w[2] )
        return 0 ;

return 1 ;
}

Laut C99 ist es sicher, von einem Union-Mitglied zu lesen, das nicht das letzte Mal verwendet wurde, um einen Wert darin zu speichern.

Wenn der zum Lesen des Inhalts eines Union-Objekts verwendete Member nicht mit dem zuletzt zum Speichern eines Werts im Objekt verwendeten Member identisch ist, wird der entsprechende Teil der Objektdarstellung des Werts als Objektdarstellung im neuen Typ as neu interpretiert wie in 6.2.6 beschrieben (ein Prozess, der manchmal als “Type Punning” bezeichnet wird). Dies könnte eine Fallendarstellung sein.

1413450cookie-checkC Vorstellungsgespräch – Casting und Vergleich

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy