[알고리즘]

bit shift(비트 쉬프트)를 이용한 곱셈, 나눗셈 연산

Neo Park 2017. 3. 29. 10:02



bit 연산자는 일반적인 사칙연산, 관계 연산, 논리 연산과는 다르게,
데이터의 2진수 형태(메모리에 저장된)를 이용하여 연산을 했다.
그 중 shift operatior는 저장된 2진수의 위치를 왼쪽 또는 오른쪽으로 이동시킨다.
(이 때, bit 연산자는 실수값을 이용하면 안된다!)

복습의 의미에서

3 << 3 의 값은 얼마인가?

답) 4byte를 통해 설명해야 하나, 1byte만을 통해 설명하겠습니다.
--------------------------------------------------------------------------
3의 2진수 형태는 다음과 같다.
   
    0 0 0 0   0 0 1 1

위의 각각의 비트를 왼쪽(화살표 방향)으로 3칸씩 이동시킨다.

( 0  0 0 )   0 0 0 1  1 0 0 0

범위를 벗어난 상위 3bit는 버리고, 하위 3bit는 0으로 채웁니다.
따라서, 결과는  0 0 0 1  1 0 0 0 이고, 10진수로 변환하면 24라는 값을 얻게 됩니다.

3 << 3 은 다음의 의미를 나타나기도 합니다.

3 * 2^3 = 3 * 8 = 24

추가) 오른쪽 쉬프트 연산자는 나눗셈의 의미를 갖는다고 했습니다.

만약 24 >> 3 이라면,

24 * 1/2^3 = 24 * 1/8 = 3

---------------------------------------------------------------------------

shift operator의 이러한 성질을 이용해, 곱셈과 나눗셈을 할 수 있습니다.


※ 곱셈의 경우

5 * 4 는 5 * 2^2 (^는 제곱의 표현으로 사용함) 로 해석이 가능하고,
5 << 2 로 변환하여 사용이 가능합니다.
또한,
5 * 5 는 5 * ( 4 + 1 ) 의 형태입니다. 따라서, 5 * ( 2^2  + 2^0 ) 이므로,
(5 << 2) + (5 << 1) 의 형태로 변환하여 사용이 가능합니다.


※ 나눗셈의 경우

5 / 4 는 5 / (2 ^ 2) 로 해석이 가능하고
5 >> 2 로 변환하여 사용이 가능합니다.
결과는 2진수 형태는 0 0 0 0  0 0 0 1 이 되고, 10진수 값으로는 1입니다.
이 때, 정수연산의 나눗셈이므로 나머지는 신경쓰지 않습니다.


http://KarmaInEarth.tistory.com


출처: http://karmainearth.tistory.com/156 [지구별 인연]