C面试 – 铸造和比较

我面临一个棘手的（海事组织）问题。 我需要以最有效的方式比较两个MAC地址 。

在那个时刻，我唯一想到的只是一个小小的解决scheme – 一个循环，比较位置，所以我做了，但是面试官的目标是投射。

MAC定义：

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

而function是（我被要求执行的）：

 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都是整数types，所以铸造是合法的，但是在描述的情况下会发生什么？

Answer 1

如果他真的不满意这个方法（这本质上是一个大脑放屁，因为你没有比较兆字节或千兆字节的数据，所以在这种情况下，不应该真的担心“效率”和“速度”），只是告诉他你相信标准库的质量和速度：

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

Answer 2

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

正确的初始方法是将MAC地址存储为uint64_t ，至less在内存中。 然后比较将是微不足道的，可以有效地实施。

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

高效实现没有任何问题，因为你知道这已经被确定为多次被称为热代码。 无论如何，对于面试问题来说，还有其他的限制。

由于短路评估，即使不按照这种方式进行编译，逻辑“与”也是先验的分支指令，所以我们不需要它。 我们也不需要把我们的返回值转换成真正的bool（ true或false ，而不是0或任何非零值 ）。

这是一个32位的快速解决scheme：XOR将捕获差异，OR将logging两个部分的差异，而不会将条件否定为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 } 

Answer 5

这将在大多数系统上运行，并且比你的解决scheme更快。

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

也可以很好地embedded，可以在系统的循环中心使用，你可以检查细节是否可行。

Answer 6

非便携式浇铸解决scheme。

在一个我使用的平台（基于PIC24）中，有一个int48types，所以作出一个安全的假设char是8位和通常的alignment要求：

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

---

当然，这在许多平台上都是不可用的，但是依赖于假定的int大小， no padding等等，一些不便携的解决scheme也是如此。

@ H2CO3提供的memcmp()是最好的便携式解决scheme（以及合理的编译器）。

如Kerrek SB所build议的那样，使用更高的devise级别并使用足够宽的整数types（如uint64_t而不是struct macA是非常有吸引力的。

Answer 7

你有一个MAC结构（包含一个6字节的数组）

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

这与关于定长字节数组的typedef的文章是一致的。

天真的做法是假定MAC地址是字alignment的（这可能是访问者想要的），尽pipe没有保证。

 typedef unsigned long u32; typedef signed long s32; typedef unsigned short u16; typedef signed short s16; int MACcmp(MAC* mac1, MAC* mac2) { if(!mac1 || !mac2) return(-1); //check for NULL args u32 m1 = *(u32*)mac1->data; U32 m2 = *(u32*)mac2->data; if( m1 != m2 ) return (s32)m1 - (s32)m2; u16 m3 = *(u16*)(mac1->data+4); u16 m2 = *(u16*)(mac2->data+4); return (s16)m3 - (s16)m4; } 

稍微安全的是将char [6]解释为short [3]（MAC更可能在偶数字节边界上alignment而不是奇数），

 typedef unsigned short u16; typedef signed short s16; int MACcmp(MAC* mac1, MAC* mac2) { if(!mac1 || !mac2) return(-1); //check for NULL args u16* p1 = (u16*)mac1->data; u16* p2 = (u16*)mac2->data; for( n=0; n<3; ++n ) { if( *p1 != *p2 ) return (s16)*p1 - (s16)*p2; } return(0); } 

假设没有，并复制到字alignment的存储，但这里的types转换的唯一原因是满足面试官，

 typedef unsigned short u16; typedef signed short s16; int MACcmp(MAC* mac1, MAC* mac2) { if(!mac1 || !mac2) return(-1); //check for NULL args u16 m1[3]; u16 p2[3]; memcpy(m1,mac1->data,6); memcpy(m2,mac2->data,6); for( n=0; n<3; ++n ) { if( m1[n] != m2[n] ) return (s16)m1[n] - (s16)m2[n]; } return(0); } 

节省大量的工作，

 int MACcmp(MAC* mac1, MAC* mac2) { if(!mac1 || !mac2) return(-1); return memcmp(mac1->data,mac2->data,6); } 

Answer 8

函数memcmp最终会自行完成循环。 所以通过使用它，你基本上只会使效率降低（由于附加的函数调用）。

这是一个可选的解决scheme：

 typedef struct { int x; short y; } MacAddr; int isEqual(MAC* addr1, MAC* addr2) { return *(MacAddr*)addr1 == *(MacAddr*)addr2; } 

由于MacAddr结构包含两个字段，因此编译器很可能将此代码转换为两个比较。

腔：除非你的CPU支持未alignment的加载/存储操作，addr1和addr2必须alignment到4个字节（即它们必须位于可被4整除的地址中）。 否则，执行该function时很可能会发生内存访问冲突。

您可以将结构划分为每个2个字节的3个字段或每个1个字节的6个字段（将alignment限制分别减less为2或1）。 但是请记住，源代码中的单个比较不一定是可执行映像（即运行时）中的单个比较。

顺便说一句，未alignment的加载/存储操作本身可能会增加运行时延迟，如果他们需要更多的“pipe”在CPUpipe道。 这实际上是一个CPU架构的问题，我怀疑他们打算在你的求职面试中“深入”。 但是，为了断言编译的代码不包含这样的操作（如果确实是“昂贵的”），你可以确保variables总是alignment到8个字节，并添加一个#pragma（编译器指令）告诉编译器“不要担心这个“。

Answer 9

可能是他想到了使用无符号字符的MAC的定义，并且正在考虑：

int isEqual(MAC* addr1, MAC* addr2) { return strncmp((*addr1).data,(*addr2).data,6)==0; }

这意味着从（无符号字符*）到（char *）的强制转换。 无论如何坏的问题。

Answer 10

要正确input双精度，你必须使用联合。 否则，你会打破某些编译器遵循的规则严格别名，结果将是不确定的。

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

根据C99，从工会会员那里读取并不是最后一次存储值。

如果用于读取联合对象内容的成员与上次用于在对象中存储值的成员不相同，则该值的对象表示forms的适当部分将被重新解释为新types中的对象表示forms，如如6.2.6所述（一个有时称为“types双关”的过程）。 这可能是一个陷阱代表。