2진 다항식의 곱셈

아래 규칙을 만족하는 이진 다항식의 곱 프로그램을 작성하라.

   A. 다항식의 모든 항의 계수는 0 또는 1로 구성된다.

   B. 동일한 지수를 갖는 항의 합과 차는 exclusive-or 연산으로 구성된다.(x숫자 = x^숫자)

      • (x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2

      • (x6 + x4 + x2 + x + 1) - (x7 + x + 1) = x7 + x6 + x4 + x2

   C. 다항식의 곱은 일반적인 방법을 따른다. 단, 항의 합과 차는 B의 규칙을 따른다.

      • (x6 + x4 + x2 + x + 1)(x7 + x + 1) =

             x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

   D. 다항식의 표현: 다항식에서 가장 큰 항의 차수가 d라고 가정할 때, d와 d+1개의

      이진수로 표현 (d <= 15) ← 각 다항식은 하나의 unsigned int로 표현

      • 예: x7 + x6 + 1 → 7 1 1 0 0 0 0 0 1

   문제: 두 개의 다항식 f(x)와 g(x)를 입력받아, f(x)g(x)를 출력

   동작 과정의 예:

   입력:

      6 1 0 1 0 1 1 1

      7 1 0 0 0 0 0 1 1

   출력:

      x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

#include <stdio.h>

void polymult(int p1d, int p1b, int p2d, int p2b, int *p3d, int *p3b) {

    int i, x=0;

    //printf("p1d %d p1b %p p2d %d p2b %p", p1d, p1b, p2d, p2b);

    for(i=0;i<p2d+1;++i) if(1 & p2b>>(p2d-i)) x=x ^ p1b<<(p2d-i);    

    *p3d = p1d+p2d;

    *p3b=x;

}

void polyprint(int pd, int pb) {

    int i;

    //printf("**pd %d pb %p ",pd,pb);

    if(pd>0) printf("x%d",pd);

    for(i=1;i<pd;++i) {

        if(1 & pb>>(pd-i)) printf(" + x%d", pd-i);

    }

    if(1 & pb) {

        if(pd>0) printf(" + 1");

        else printf("1");

    }

    printf("\n");

}

int main() {

    // p1d - 다항식1의 차수 p1b - 다항식1의 데이터 p2, p3도 마찬가지 입니다.

    int p1d, p1b, p2d, p2b, p3d, p3b;

    int i, d, x, b;

    b=0;

    printf("다항식1 입력: ");

    scanf("%d", &d);

    for(i=0;i<d+1;++i) {

        scanf("%d", &x);

        b=b<<1 | x;

    }

    p1d=d;

    p1b=b; 

    printf("다항식1 : ");

    polyprint(p1d, p1b);

    b=0;

    printf("다항식2 입력: ");

    scanf("%d", &d);

    for(i=0;i<d+1;++i) {

        scanf("%d", &x);

        b=b<<1 | x;

    }

    p2d=d;

    p2b=b; 

    printf("다항식2 : ");

    polyprint(p2d, p2b);

    polymult(p1d, p1b, p2d, p2b, &p3d, &p3b);

    printf("다항식3 : ");

    polyprint(p3d, p3b);

    return 0;

}