[4. 기본자료형] 4.6 산술 연산자 없이 나눗셈 계산하기

---

Q 4.6 산술 연산자 없이 나눗셈 계산하기

양의 정수 x와 y를 나눈 몫을 구하라. (제목은 산술 연산자 없이 이지만 덧셈, 뺄셈, 쉬프트 연산은 허용한다.)

---

x = 50 에서 y = 4을 나눈다고 할때 다음과 같다.
< x = 110010 / y = 100 > 이때 y의 비트 자릿수를 x와 동일하게 만들어 빼준다.
    110010
-   100000   ...1번
---------------
      10010      1번의 값 100000 을 결과값에 저장. 그후 y의 자릿수를 10010과 동일하게 만들어 빼준다.
-     10000   ...2번
--------------- 
            10      2번의 값 10000 을 결과값에 저장. (결과값 = 몫) 남은값을 y와 비교해 작으면 결과값을 리턴한다.

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

시간복잡도 O(n)

50/6 = 8(몫)