[4. 기본자료형] 4.5 곱셈과 덧셈 없이 x dot y 계산하기

---

Q 4.5 곱셈과 덧셈 없이 x dot y 계산하기

저전력 기기의 프로세서에 곱셈 연산기가 없는 경우가 종종있다.
이때 로우 레벨의 원시적인 방법을 사용하여 음이아닌 정수 두개의 곱셈 연산 알고리즘을 직접 작성해보자.
(대입 연산자, [>>, <<, |, &, ~, ^]와 같은 비트연산자, 동등성 확인과 불 조합 연산을 사용하자)
(루프와 함수도 직접 작성해야하며, 증감 연산자와 비교연산도 불가능 하다.)

---

먼저 덧셈 연산을 만들자. 13과 9를 더할때 다음과 같이 표현할 수 있다.
13 = 1101, 9 = 1001 이므로 올림이 일어나는 자리를 먼저 판단한다.
        1101
&      1001
---------------
        1001     이다.  자리가 올라갔으므로 << 1 을 적용해 10010 으로 사용한다.
올림이 일어나지 않는 자리를 판단한다.(1 + 0 이거나 0 + 0 인 자리판단)
        1101
^      1001
---------------
        0100   이다.
두수를 xor연산하면 10010 ^ 0100 = 10110 = 22 이다.

해당 코드는 다음과 같다.

덧셈 시간복잡도 O(n)

곱셈 연산은 위에서 만들어둔 덧셈 연산을 이용한다.
13과 9를 곱할때 다음과 같이 표현할 수 있다.
13 = 1101, 9 = 1001 이므로 1101 의 자리의 숫자 x 1001 을 모두 더하는 방법을 사용한다.
예를들면
           1101
x         1001
------------------
           1001     .....1번
         0000       .....2번
      1001          .....3번
+  1001            .....4번
------------------
    1110101 과 같은 방법을 사용한다.
1번+2번+3번+4번 을 할것이며, 2번은 모두0이므로 넘어간다.
3번은 자리가 2개 앞이므로 <<2 를 적용, 4번은 <<3 을 적용해 더하면 된다.

해당 코드와 코딩결과는 다음과 같다.

곱셈 (덧셈을 n번 반복)

시간복잡도 O(n^2)