C工作面试 - 铸造和比较

Question

我遇到了一个棘手的(IMO)问题.我需要以最有效的方式比较两个MAC地址.

在那一刻我唯一想到的想法是微不足道的解决方案 - 一个for循环,比较位置,所以我做了,但面试官的目标是铸造.

MAC定义:

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

功能是(我被要求实施的那个):

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

但如上所述,他的目标是铸造.

意思是,以某种方式将给定的MAC地址转换为int,比较两个地址,然后返回.

但是在投射时int int_addr1 = (int)addr1;,只会投入四个字节,对吗？我应该检查其余的吗？含义位置4和5？

这两个char和int是整数类型,因此铸造是合法的,但在所描述的情况,会发生什么？

Answer 1

如果他真的不满意这种方法(这实际上是一个脑屁,因为你没有比较兆字节或千兆字节的数据,所以在这种情况下,人们不应该真的担心"效率"和"速度"),告诉他你相信标准库的质量和速度:

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

Answer 2

如果你的面试官要求你产生不明确的行为,我可能会在其他地方寻找工作.

正确的初始方法是将MAC地址存储uint64_t在至少内存中.然后比较将是微不足道的,并且可以有效地实现.

Answer 3

牛仔时间:

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 4

有效的实现没有任何问题,因为你知道这已被确定为多次调用的热代码.在任何情况下,面试问题都可以有奇怪的限制.

逻辑AND是由于短路评估的先验分支指令,即使它不以这种方式编译,所以让我们避免它,我们不需要它.我们也不需要将返回值转换为真正的bool(true或false,不是0或任何非零值).

这是32位的快速解决方案:XOR将捕获差异,OR将记录两个部分的差异,NOT将否定条件为EQUALS,而不是UNEQUAL.LHS和RHS是独立的计算,因此超标量处理器可以并行执行此操作.

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

编辑
上述代码的目的是表明这可以在没有分支的情况下有效地完成.评论指出这个C++将其归类为未定义的行为.虽然如此,VS处理这个问题.在不更改访问者的结构定义和函数签名的情况下,为了避免未定义的行为,必须进行额外的复制.因此,没有分支但具有额外副本的非未定义行为方式如下:

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
}