[divide two integers] solution (using bit operator) 비트연산자 활용한 이진수의 나눗셈

https://leetcode.com/problems/divide-two-integers/description/

Divide Two Integers - LeetCode

리트코드의 나눗셈 구현문제를 풀어봤다.
상당히 졸린 관계로 자세한 풀이는 추후에 수정하고 이진법의 나눗셈 원리를 이해할 수 있도록 정리한 필기를 공유해본다.

나눗셈이 뺄셈의 고차원적 표현이라는 건 모두가 알고 있겠지만 count++만 하기에는 인생이 너무 짧다

고대 이집트에서부터 지금까지 이어진 기나긴 창조적 게으름의 발명으로 인해 만들어진 것들이 놀랍게도 나눗셈의 세로계산인데 우리는 익숙함에 속아 소중함을 잊은 거다...


우선 십진법의 세로계산 원리를 되짚어보자

핵심은 자릿수 비교다
111/3을 하면
1) 1과 3 비교
2) 11과 3 비교-> 해당 자릿수에서 몫 구하기
3) 이하동일

이런 방식으로 진행된다
이 로직을 이진법에 적용하면

예를 들어 1101 / 10 이라면
1) 1101의 11과 나누는 수 10 비교->해당 자릿수에서 몫 구하기
2)이하동일

앞서 들었던 십진법과 다를 바 없이 이런 식으로 진행될 것이다

문제는 우리가 주어지는 Integer의 자릿수를 모른다는 것인데

그래서 while문을 돌려가며 비트연산자 <<를 활용해 나누는 수의 자릿수를 변경해주었다

자릿수만 안다면 두 인티저를 결합하는 방식으로도 풀이할 수ㅠ있겠지만 그 풀이는 다음에...

하여튼 결론은 십진법의 나눗셈 방식을 살짝만 변형해도 이진법 나눗셈을 구현할 수 있다는 것이다.


맨날 과외아가한테 수학 가르치면서 쉬운 예시로 생각해보고 적용하라고 입에 닳도록 말했는데 나부터 실천해야겠다.. 반성