C entrevue d'emploi de moulage et de comparer

Question

J'ai été confronté à un épineux (OMI) en question. J'avais besoin de comparer deux adresses MAC, dans la manière la plus efficace.

La seule pensée qui traversa mon esprit en ce moment est la solution triviale - for boucle, et en comparant les lieux, et je l'ai fait, mais l'enquêteur avait pour objectif de casting.

Le MAC définition:

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

Et la fonction est (celui que j'ai été invité à mettre en œuvre):

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;
}

Mais comme mentionné, il avait en vue pour la coulée.

Le sens en quelque sorte jeté l'adresse MAC donnée à un int, comparer les deux adresses, et retour.

Mais lors de la coulée, int int_addr1 = (int)addr1;, seulement quatre octets sera coulé, non? Dois-je vérifier les autres? Sens emplacements 4 et 5?

Les deux char et int sont des types d'entiers, de sorte casting est légal, mais ce qui se passe dans la situation décrite?

Answer 1

Si votre interlocuteur exige de vous produire un comportement indéfini, je serais probablement chercher un emploi ailleurs.

La bonne première approche serait de stocker l'adresse MAC dans quelque chose comme un uint64_t, au moins en mémoire. Ensuite, les comparaisons triviales, et mises en œuvre efficacement.

Answer 2

Cowboy le temps:

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);
}

Answer 3

Il n'y a rien de mal avec une mise en œuvre efficace, pour tout ce que vous savez ce qui a été déterminé à être chaud le code qui est appelé de nombreuses fois. Et dans tous les cas, son correct pour des questions d'entrevue d'avoir bizarre contraintes.

Logique ET, a priori, une ramification de l'instruction en raison de court-circuit d'évaluation, même si cela ne compile pas de cette façon, donc permet de l'éviter, nous n'avons pas besoin il. Nous ne devons convertir notre valeur de retour d'un vrai booléen (vrai ou faux, pas de 0 ou de tout ce qui n'est pas zéro).

Voici une solution rapide sur 32 bits: XOR permettra de saisir les différences, OU va enregistrer de la différence dans les deux parties, et non PAS réduit à néant la condition dans d'égal à ÉGAL, pas l'INÉGALITÉ. La LHS et RHS sont calculs indépendants, si un superscalar processeur peut le faire en parallèle.

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

MODIFIER
Le but de ce code est de montrer que cela peut être fait de manière efficace, sans ramification. Commentaires l'ont souligné cette C++ de la classe ce qu'un comportement indéfini. Si cela est vrai, VS gère cela très bien. Sans changer l'enquêteur de la structure de la définition et de la fonction de signature, afin d'éviter un comportement indéfini, un exemplaire supplémentaire doit être faite. Ainsi, le non-comportement indéfini sans ramification, mais avec une copie supplémentaire serait comme suit:

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
}

Answer 4

Ce serait de travailler sur la plupart des systèmes,et être plus rapide que votre solution.

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

serait inline bien, pourrait être à portée de main au centre de la boucle sur un système où vous pouvez vérifier les détails sont viables.