fits_bits 함수

다음과 같은 프로토타입을 갖는 함수를 작성하시오.

return 1 when x can be represented as an n-bit, 2's complement number;

0 otherwise Assume 1 <= n <= w, 여기서 w=sizeof(int)*8

int fits_bits(int x, int n);

* 조건문,루프,SWITCH,함수,매크로 호출,나눗셈,MOD,<,>등 관계비교연산자 금지

* 비트수준 논리연산, 좌측,우측 쉬프트, 덧셈,뺄셈, ==과 !=, 캐스팅 허용

* 정수는 2의 보수 형태로 나타낸다, 부호형 데이터의 우측 쉬프트는 산술적으로, 

여기까지가 문제입니다.

===================================================================

네이버 지식인 ghldhr00 님의 답변을 기초로한 것입니다.

http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=180926760

#include <stdio.h>

#define w (sizeof(int) * 8)                       // int 형의 비트 크기

int fits_bits(int x, int n) {

    // 부호있는 정수 x를 부호없는 정수 ux 로 옮겨줍니다.

    unsigned int ux = (unsigned int) x;   // unsigned x

 

    //  NNNN은 n비트로 나타낸 부분이라고 하겠습니다. [아래에서 n은 4인 경우]

    // M'MMM MMMM MMMM MMMM MMMM MMMM MMMM NNNN

    // 여기서 M'과 M이 같다면 오버플우가 아닙니다.

    // ux<<1을 하면

    //     MMMM MMMM MMMM MMMM MMMM MMMM MMMN NNN0 이 되고

    // 이를 >>n 하면

    //     0000 MMMM MMMM MMMM MMMM MMMM MMMM MMMN 이 됩니다. [1]

    //     바로 위에서 x가 양수일때 오버플로우가 안될려면 M', M, N 모두 0이라야 한다. [처음 N]

    //                       x가 음수일때 오버플로우가 안될려면 M', M, N 모두 1이라야 한다. [처음 N]

    //                                  이 경우 n개의 0 다음에는 모두 1이 와야 한다.

    // M' 이 1일경우:

    //     M'<<(w-n)을 하면 

    //           0001 0000 0000 0000 0000 0000 0000 0000 이 되고

    //           M'을 빼주면

    //           0000 1111 1111 1111 1111 1111 1111 1111 이 됩니다. [2]

    //                   n개의 0다음에는 모두 1이 옵니다.

    //  [1], [2] 로 부터 M'이 0이든 1이든 서로 같다면 오버플로우가 아닙니다.

    unsigned int mm = (ux << 1) >> n;   // MMMM...M

    unsigned int mp = ux >> (w-1);         // mp는 부호 비트 0또는 1

    printf("ux=%08x\n", ux);

    printf("mm=%08x\n", mm);

    printf("mp=%08x\n", mp);

    printf("mp<<(w-n)=%08x\n", mp<<(w-n));

    return mm == (mp << (w-n)) - mp;

}

int main() {

    int x, n;

    while(1) {

        printf("x n 입력: ");

        scanf("%d%d", &x, &n);

        if(x==0) { break; }

        if(fits_bits(x, n)) {

            printf("fits\n");

        } else {

            printf("not\n");

        }

    }

    return 0;

}

위의 프로그램에서 n의 값이 w의 값과 같을 경우는 fits_bits가 정상적으로 동작하지 않습니다.

그 이유는 x<<y 에서 y의 값이 w일 경우에는 연산이 정의가 되지 않기 때문인 것으로 보입니다.

return (n==w) | (mm == (mp << (w-n)) - mp); 로 고치면 이문제가 해결되는 군요!