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

만약 당신의 면접관이 당신에게 정의되지 않은 행동을 요구한다면, 저는 아마도 다른 곳에서 일자리를 찾을 것입니다.

주소로 입니다.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는 이렇게 컴파일되지 않더라도 단락평가에 의한 분기명령이기 때문에 회피합시다.또, 반환치를 진정한 부울(참 또는 거짓, 0이 아닌 것)로 변환할 필요도 없습니다.

32비트에 관한 고속 솔루션을 다음에 나타냅니다.XOR은 차분을 취득하거나 양쪽의 차이를 기록하지만, 조건을 EQUAL이 아닌 EQUAL로 부정하지 않습니다.LHS와 RHS는 독립된 계산이므로 슈퍼스케일러 프로세서는 이를 병렬로 실행할 수 있습니다.

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

★★★★
상기 코드의 목적은 분기 없이 효율적으로 실행할 수 있음을 보여주는 것이었습니다.코멘트에서는, 이 C++가 이것을 정의되지 않은 동작으로 분류하고 있다고 지적되고 있습니다.비에스에스에스에스에이에이면접관의 구조 정의와 함수 서명을 변경하지 않고 정의되지 않은 동작을 방지하기 위해 추가 복사본을 만들어야 합니다.따라서 분기하지 않고 추가 복사본을 사용하는 정의되지 않은 동작 방식은 다음과 같습니다.

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 베이스」, 「PIC24 베이스).int48char요건입니다.이거는 8비트입니다.

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

---

할 수 , 되는 「」에 휴대할 수 .그러나, 상정되는 상황에 따라서는, 포터블이 아닌 솔루션도 다수 있습니다.int ★★★★★no padding 등등.

솔루션 컴파일러가은 「」입니다.memcmp()@H2CO3입니다.

하세요.uint64_tstruct macA케렉 SB

타이프 펀닝을 올바르게 하려면 유니언을 사용해야 합니다.그렇지 않으면 특정 컴파일러가 따르는 규칙의 엄밀한 에일리어스를 위반하여 결과가 정의되지 않습니다.

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

유니언 오브젝트의 내용을 읽기 위해 사용된 부재가 오브젝트 내의 값을 기억하기 위해 마지막으로 사용된 부재와 동일하지 않은 경우, 그 값의 오브젝트 표현 중 적절한 부분을 6.2.6에 기술된 새로운 타입의 오브젝트 표현으로 재해석한다('타입 펀닝'이라고도 함).이것은 트랩 표현일 수 있습니다.

MAC 구조(6바이트 배열 포함),

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

이는 고정 길이 바이트 배열의 typedef에 대한 이 기사와 일치합니다.

순진한 접근법은 MAC 주소가 단어에 맞춰져 있다고 가정하는 것입니다(아마도 인터뷰 진행자가 원하는 것일 것입니다).단, 보증은 되지 않습니다.

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

문자[6]를 짧은[3]로 해석하는 것이 조금 안전합니다(MAC는 홀수보다 짝수 바이트 경계에 정렬될 가능성이 높습니다).

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

아무것도 상정하지 않고 워드 배열 스토리지로 복사하지만, 여기서 타이프 캐스팅을 하는 유일한 이유는 인터뷰 진행자를 만족시키기 위해서입니다.

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

함수 memcmp는 최종적으로 루프 자체를 수행합니다.따라서 이 기능을 사용하면 기본적으로 (기능 호출이 추가되어) 효율이 떨어집니다.

옵션 솔루션은 다음과 같습니다.

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

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

MacAddr 구조에는 두 개의 필드가 포함되어 있기 때문에 컴파일러는 이 코드를 두 개의 비교로 변환합니다.

충치: CPU가 정렬되지 않은 로드/스토어 조작을 지원하지 않는 한 addr1과 addr2는 4바이트로 정렬해야 합니다(즉, 4로 나눌 수 있는 주소에 배치해야 합니다).그렇지 않으면 기능이 실행될 때 메모리 액세스 위반이 발생할 수 있습니다.

구조를 2바이트씩 3개의 필드 또는 1바이트씩 6개의 필드로 분할할 수 있습니다(각각 정렬 제한을 2 또는 1로 줄임).그러나 소스 코드의 단일 비교가 반드시 실행 가능 이미지(즉, 실행 시)의 단일 비교가 되는 것은 아니라는 점에 유의하십시오.

BTW, 정렬되지 않은 로드/스토어 작업 자체가 CPU 파이프라인에서 더 많은 "nops"를 필요로 하는 경우 런타임 지연을 추가할 수 있습니다.이것은 CPU 아키텍처의 문제입니다.취업 면접에서 그렇게까지 파고들 생각은 없었던 것 같습니다.그러나 컴파일된 코드에 이러한 연산이 포함되어 있지 않다고 단언하기 위해(실제로 "비싼" 경우) 변수는 항상 8바이트로 정렬되도록 하고 컴파일러에 "이것에 대해 걱정하지 말라"는 #pragma(컴파일러 지시문)를 추가할 수 있습니다.

그는 부호 없는 문자를 사용하는 MAC의 정의를 염두에 두고 다음과 같이 생각하고 있었을 가능성이 있습니다.

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

즉, (부호된 문자*)에서 (문자*)로의 캐스트를 의미합니다.어쨌든 나쁜 질문이야.

덧붙여서, 퍼포먼스의 해답을 진정으로 요구하고 있는 유저에게 있어서, 다음의 것은 브랜치리스입니다.또, 1 문자당 1 개의 페치수를 늘리는 한편, 모두 같은 캐시 라인으로부터 취득하는 것이 좋기 때문에, 그다지 비싸지 않습니다.

int isEqual(MAC* addr1, MAC* addr2)
{
    return
      (addr1->data[0] == addr2->data[0])
    & (addr1->data[1] == addr2->data[1])
    & (addr1->data[2] == addr2->data[2])
    & (addr1->data[3] == addr2->data[3])
    & (addr1->data[4] == addr2->data[4])
    & (addr1->data[5] == addr2->data[5])
    ;
}

라이브(브런치리스)로 표시

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