C 면접-캐스팅 및 비교

C 면접-캐스팅 및 비교

---

나는 까다로운 (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;
}

하지만 언급했듯이 그는 캐스팅을 노리고 있었다.

의미, 어떻게 든 int에 주어진 MAC 주소를 캐스팅하고 두 주소를 비교하고 반환합니다.

하지만 캐스팅 할 때, int int_addr1 = (int)addr1;4 바이트 만 캐스팅 됩니다. 나머지는 확인해야하나요? 위치 4와 5를 의미합니까?

char및 둘 다 int정수 유형이므로 캐스트가 합법적이지만 설명 된 상황에서 어떤 일이 발생합니까?

---

그가이 접근 방식에 정말 만족하지 못한다면 (메가 바이트 나 기가 바이트의 데이터를 비교하지 않기 때문에 본질적으로 두뇌 방귀입니다. 따라서이 경우에는 "효율"과 "속도"에 대해 걱정할 필요가 없습니다.) 표준 라이브러리의 품질과 속도를 신뢰한다고 말하십시오.

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

---

면접관이 정의되지 않은 행동을 요구한다면 다른 곳에서 일자리를 찾을 것입니다.

올바른 초기 접근 방식은 MAC 주소 uint64_t를 최소한 인 메모리 와 같은 것에 저장하는 것 입니다. 그러면 비교는 사소하고 효율적으로 구현할 수 있습니다.

---

카우보이 시간 :

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

---

효율적인 구현에는 잘못된 것이 없습니다. 여러분이 아는 모든 것은 이것이 여러 번 호출되는 핫 코드로 결정 되었기 때문입니다. 그리고 어쨌든 인터뷰 질문에 이상한 제약이 있어도 괜찮습니다.

논리 AND는 이런 식으로 컴파일하지 않더라도 단락 평가로 인한 분기 명령이므로 피하자, 필요하지 않다. 또한 반환 값을 true bool ( true 또는 false , 0 또는 0이 아닌 항목 ) 으로 변환 할 필요가 없습니다 .

다음은 32 비트에 대한 빠른 솔루션입니다. XOR은 차이를 캡처하거나 두 부분의 차이를 기록하고 NOT은 조건을 UNEQUAL이 아닌 EQUALS로 부정합니다. 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
}

---

이것은 대부분의 시스템에서 작동하며 솔루션보다 빠릅니다.

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

세부 사항이 실행 가능한지 확인할 수있는 시스템의 루프 중심에서 편리하게 인라인 할 수 있습니다.

---

비 휴대용 주조 솔루션.

내가 사용하는 플랫폼 (PIC24 기반)에는 유형 int48이 있으므로 안전한 가정 char은 8 비트이며 일반적인 정렬 요구 사항은 다음과 같습니다.

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

---

물론 이것은 많은 플랫폼에서 사용할 수 없지만 가정 된 int크기 no padding등에 따라 이식 할 수없는 여러 솔루션도 마찬가지입니다 .

최고의 휴대용 솔루션 (좋은 컴파일러를 고려할 때 상당히 빠름)은 memcmp()@ H2CO3 에서 제공하는 것입니다.

더 높은 디자인 수준으로 이동하고 Kerrek SB가 제안한대로 uint64_t대신. 와 같이 충분히 넓은 정수 유형을 사용하는 struct macA것은 매우 매력적입니다.

---

유형 punning을 올바르게 수행하려면 공용체를 사용해야합니다. 그렇지 않으면 특정 컴파일러가 따르는 엄격한 별칭 규칙을 위반하고 결과가 정의되지 않습니다.

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에 따르면 값을 저장하는 데 마지막으로 사용되지 않은 공용체 멤버에서 읽는 것이 안전합니다.

If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

---

You have a MAC structure (which contains an array of 6 bytes),

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

Which agrees with this article about typedef for fixed length byte array.

The naive approach would be to assume the MAC address is word aligned (which is probably what the interviewer wanted), albeit not guaranteed.

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

Slightly safer would be to interpret the char[6] as a short[3] (MAC more likely to be aligned on even byte boundaries than odd),

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

Assume nothing, and copy to word aligned storage, but the only reason for typecasting here is to satisfy the interviewer,

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

Save yourself lots of work,

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

---

Function memcmp will eventually do the loop itself. So by using it, you would basically just make things less efficient (due to the additional function-call).

Here is an optional solution:

typedef struct
{
    int x;
    short y;
}
MacAddr;

int isEqual(MAC* addr1, MAC* addr2)
{
    return *(MacAddr*)addr1 == *(MacAddr*)addr2;
}

The compiler will most likely convert this code into two comparisons, since the MacAddr structure contains two fields.

Cavity: unless your CPU supports unaligned load/store operations, addr1 and addr2 must be aligned to 4 bytes (i.e., they must be located in addresses that are divisible by 4). Otherwise, a memory access violation will most likely occur when the function is executed.

You may divide the structure into 3 fields of 2 bytes each, or 6 fields of 1 byte each (reducing the alignment restriction to 2 or 1 respectively). But bare in mind that a single comparison in your source code is not necessarily a single comparison in the executable image (i.e., during runtime).

BTW, unaligned load/store operations by themselves may add runtime latency, if they require more "nops" in the CPU pipeline. This is really a matter of CPU architecture, which I doubt they meant to "dig into" that far in your job interview. However, in order to assert that the compiled code does not contain such operations (if indeed they are "expensive"), you could ensure that the variables are always aligned to 8 bytes AND add a #pragma (compiler directive) telling the compiler "not to worry about this".

---

May be he had in mind a definition of MAC that used unsigned char and was thinking to:

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

which implies a cast from (unsigned char *) to (char *). Anyway bad question.

참고URL : https://stackoverflow.com/questions/20858876/c-job-interview-casting-and-comparing