쉬프트 연산과 곱셈


비트를 이동시키는 쉬프트 연산은 곱셈과 나눗셈의 대용으로 사용할 수 있다. 다음 예제를 실행해 보아라.

 

: shiftmulti

#include <Turboc.h>

 

void main()

{

     int i;

 

     printf("정수를 입력하세요 : ");

     scanf("%d",&i);

     printf("결과=%d\n",i << 1);

}

 

정수 i를 입력받은 후 왼쪽으로 한칸 쉬프트한 값을 출력했다. 실행해 보면 알겠지만 입력한 수의 정확하게 2배되는 값이 출력된다. 5를 입력하면 10, 100을 입력하면 200이 출력될 것이다. 정수를 왼쪽으로 한칸 쉬프트하면 두배가 되며 오른쪽으로 한칸 쉬프트하면 절반이 되는데 어째서 그런지 보자. 입력값이 5였다고 가정하면 이 값은 이진수로 0101인데 이 값을 10진수로 바꾸는 공식은 다음과 같다.

 

1*22+0*21+1*20 = 5

 

이진수의 각 자리수는 2의 거듭승에 해당하는 값을 표현한다. 그런데 비트를 왼쪽으로 한칸 이동시키면 모든 자리수의 지수가 1 올라가기 때문에 2배가 된다. 쉬프트한 결과는 1010이며 이 값은 다음과 같이 10진수로 바꿀 수 있다.

 

1*23+0*22+1*21+0*20 = 10

 

그래서 왼쪽으로 한칸 쉬프트하면 두배가 되는 것이다. 단, 용량 한계를 넘어서는 값은 잘려 나가는데 이는 어쩔 수 없다. 예를 들어 16비트 정수 40000을 왼쪽으로 쉬프트하면 80000이 되는데 16비트로는 이 값을 표현할 수 없으므로 제일 오른쪽의 1이 밀려나고 결과는 14464가 된다. 이 값은 80000-65536인데 밀려나서 버려진 오른쪽 비트의 값이 65536이기 때문이다. 32비트의 int형을 쓰면 웬만큼 큰 수라도 용량의 한계를 넘지 않을 것이다.

왼쪽으로 쉬프트하는 연산이 값을 두배로 만드는데 비해 오른쪽으로 쉬프트하는 연산은 값을 절반으로 만든다. 모든 자리수의 지수가 1 감소하기 때문이다. 이진수 1100을 오른쪽으로 쉬프트하면 0110이 되는데 이 값은 처음값 12의 절반인 6이다. 동일한 원리이므로 따로 그림까지 그릴 필요는 없을 것 같다.

오른쪽 쉬프트는 자리 넘침이 발생하지 않지만 오른쪽으로 밀려나 사라지는 값만큼 오차가 생길 수는 있다. 짝수를 밀면 정확하게 절반이 되지만 홀수를 밀면 제일 오른쪽에 있던 1이 밀려 나므로 실제값보다 0.5더 작은 값이 계산된다. 예를 들어 이진수 0111(7)을 오른쪽으로 밀면 b0가 밀려나고 0011(3)이 된다. 정확하게 계산하자면 3.5가 되어야 하지만 비트는 정수의 세계이기 때문에 밀려난 0.5는 사라지게 된다.

좌우 쉬프트 연산이 곱셈과 나눗셈 대용으로 사용될 수 있다는 것이 도저히 이해가 안간다면 아마도 2진수에 익숙하지 않아서 그럴 것이다. 그렇다면 10진수로 이 현상을 설명해 보자. 10진수 1234에서 각 자리수는 10의 거듭승에 해당하는 자리값을 가지고 있다. 1은 103인 1000자리에 있고 2는 102인 100자리에 있고 3은 101인 10자리에 있는 셈이다.

 

1234=1*103+2*102+3*101+4*100

 

이 값을 왼쪽으로 쉬프트하면 각 자리수의 지수가 1증가한 12340이 된다.

 

12340=1*104+2*103+3*102+4*101+0*100

 

천자리는 만자리로 올라가고 백자리는 천자리로 올라가므로 모든 값이 10배가 되어 전체값도 10배가 되는 것이다. 반대로 오른쪽으로 밀면 모든 자리수가 10배 감소하므로 10분의 1로 값이 줄어든다. 1234를 오른쪽으로 밀면 123이 되고 일자리에 있던 4는 밀려나 사라진다. 물론 실수 차원이라면 123.4가 되겠지만 말이다.

좀 더 쉽게 설명하자면 임의의 십진수가 있을 때 뒤에 0을 하나 더 붙이면 10배가 되고 제일 뒷자리를 제거해 버리면 약간의 오차를 제외하고 1/10로 그 값이 줄어든다. 초등학생들도(심지어 일부 유치원 아동들까지도) 아는 간단한 원리이며 일상 생활에서도 흔히 있는 연산이므로 너무 너무 당연하게 생각될 것이다. 10진수에서 쉬프트 연산이 10배씩 증감하는 것처럼 2진수에서는 쉬프트 연산이 2배씩 증감하는 것이다.

왼쪽으로 한칸 밀면 두 배가 된다. 그럼 이 수를 다시 왼쪽으로 한칸 밀면 2배의 2배, 즉 4배가 될 것이다. 다시 한 번 더 밀면 8배가 된다. 자, 그럼 이제 쉬프트 연산과 곱셈 연산의 관계를 일반화해 보자.

 

a << b == a * 2b

 

a를 b만큼 왼쪽으로 민다는 것은 a를 2의 b승만큼 곱하는 것과 같다. 이 공식은 b가 음수일 때도 똑같이 적용된다. a를 -1만큼 왼쪽으로(즉 오른쪽으로 한칸) 밀면 2-1를 곱하는(즉 2로 나누는)것과 같다. 그래서 곱셈 대신에 쉬프트 연산을 사용할 수 있는데 이 두 연산은 엄청난 속도 차이가 있다. 비트를 이동시키는 것과 일정 횟수 더하기를 반복하는 것은 CPU 입장에서 보면 완전히 다른 작업이기 때문에 속도차가 무려 10배 정도 난다. 쉬프트 연산은 전혀 논리적이지 않으며 기계적이므로 기계가 하기에는 아주 쉬운 연산인 것이다.

a*2를 한 번 할 시간이면 a << 1을 10번 정도 할 수 있다는 얘기다. 이렇게 속도차가 나기 때문에 핵심 게임 엔진이나 시스템 프로그래머들은 곱셈 대신 쉬프트 연산을 즐겨 사용한다. 중요한 루프에서 곱셈을 하느냐 쉬프트 연산을 하느냐에 따라 프로그램의 성능에 확연한 차이가 나기 때문에 쉬프트 연산은 도저히 피할 수 없는 달콤한 유혹인 것이다.

쉬프트 연산이 곱셈에 비해 불리한 점은 2의 거듭승에 대해서만 곱셈이 가능하다는 점이다. 2배, 4배, 8배, 16배 등만 할 수 있으며 3배, 17배 이런 연산은 할 수 없다. 그러나 쉬프트 연산과 덧셈, 뺄셈을 잘 조합하면 이런 연산이 가능해지기도 한다.

 

3배 : a << 1 + a;

9배 : a << 3 + a;

15배 : a << 4 - a;

60배 : a << 6 - a << 2;

 

특히 제일 마지막의 쉬프트 연산으로 60배를 하는 코드는 아주 기발한 응용예이며 감탄을 금하기 어려운 예술 코드라고 할 수 있다. 정밀하게 측정해 보면 이런 연산들이 곱셈보다 수배~수십배 더 빠르다. 보통의 경우라면 일반적인 곱셈을 하는 것이 소스를 유지하기에 편리하지만 속도가 지극히 중요하다면 곱셈보다는 가급적이면 쉬프트 연산을 사용하는 것이 좋다.

'C/C++언어' 카테고리의 다른 글

고정 소수점  (0) 2008.05.09
각 언어별 3중 포인터  (0) 2008.05.06
쉬프트 연산과 곱셈  (0) 2008.03.26
[리눅스프로그래밍] makefile  (1) 2008.03.07
ASSERT(), VERIFY(), TRACE()  (0) 2008.03.04
템플릿 사용한 max 만들기  (0) 2008.03.03

CImage는 MS에서 .net 이후부터 제공되는 그림 관련 클래스임.
이전 CBitmap의 bmp만 다루던거에서 좀더 확장하여 Png, Jpg, gif등 다양한 포멧을 지원한다.

기본적으로 사용은
CImage image; 로 한다.

CImage는 일종의 스케치북으로 볼수 있다.

사용법으로
CImage.Create(width, height, bpp); 로 새 스케치북을 만드거나
CImage.Load(CString("filename")); 으로 파일을 받아올수 있다.

이렇게 만들어진것중에서 자주 사용하는 매소드로
BitBlt ... : 기본 API 이다.
사용법은
CImage image;
image.Load("test.jpg");
image.BitBlt(pDC, 0, 0);

이러면 pDC의 0,0 지점에 test.jpg 그림이 복사된다.
좀더 응용하면

CImage a,b;
a.Load("test.jpg");
b.Create(a.GetWidth(), a.GetHeight(), a.GetBPP());
a.BitBlt(b.GetDC(), 0, 0);
b.ReleaseDC();

이렇게 하면 b에 a의 그림이 복사된다.
중요 포인트는 GetDC()를 해준뒤 바로 ReleaseDC를 해줘야 한다.

나머지 대충 사용하면되고..

GetPixel의 경우..
GetPixel과 SetPixel을 그대로 사용하는건 정말 CPU혹사시키는 짓이다.
다음 함수로 대체 하는것이 좋다

// SetPixel 대용
void PointColor(CImage *image, int x, int y, COLORREF c)
{
 // m_image.SetPixel() call ::SetPixel() which is too slow
 // since it has to work with all DCs.

 BYTE *p = (BYTE*)image->GetPixelAddress(x, y);
 if (m_nBitDepth == 16) {
  *(WORD *)p = (WORD)(((c&0xf80000) >> 19) | ((c&0xf800) >> 6) | ((c&0xf8) << 7));
 }
 else {
  *p++ = GetBValue(c);
  *p++ = GetGValue(c);
  *p = GetRValue(c);
 }
}

// GetPixel 대용
COLORREF GetPointColor(CImage *image, int x, int y)
{
 COLORREF result = *((COLORREF*)image->GetPixelAddress(x,y));

 // 메모리에서 가져올때, blue와 red위치가 바뀌어서 가져와진다
 BYTE r = GetBValue(result);
 BYTE g = GetGValue(result);
 BYTE b = GetRValue(result);
 
 return RGB(r,g,b);
}


사용자 삽입 이미지



#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

// 피보팅을 처리하는 함수 구현
void pivoting(double **matrix, int currentRow, int currentCol, int rowSize, int colSize){
 double *temp;
 temp =  new double[colSize];

 double max = fabs(matrix[currentRow][currentCol]); // 우선 현재행,현재열 값을 최대값으로 지정
 
 for(int i=currentRow+1; i<rowSize; i++){
  if(fabs(matrix[i][currentCol]) > max){
   temp = matrix[currentRow];
   matrix[currentRow] = matrix[i];
   matrix[i] = temp;
   max = matrix[currentRow][currentCol];
  }
 }
}

// 임의 크기의 행렬의 가우시안소거법 함수 구현
void gaussianElimination(double **matrix, int rowSize, int colSize){
 double temp;
 int i,j,k;

 pivoting(matrix,0,0,rowSize,colSize);

 for(i=0; i<rowSize-1; i++){
  for(j=i+1; j<rowSize; j++){

   pivoting(matrix,i,i,rowSize,colSize);

   temp = matrix[j][i] / matrix[i][i];
   for(k=0; k<colSize; k++){
     matrix[j][k] = matrix[j][k] - matrix[i][k]*temp;
   }
  }
 }

}

// 역행렬이 존재하는지 확인하는 함수 구현
int existINV(double **matrix, int size){
 double temp = 1.0;
 gaussianElimination(matrix, size, 2*size);
 for(int i=0; i<size; i++){ // 가우시안 소거법으로 상삼각 행렬을 만든후 대각요소의 곱을 구함
  temp *= matrix[i][i];
 }
 if(temp != 0) // 대각곱이 0이 아니면 역행렬이 존재하고 0이면 역행렬이 존재하지 않는다
  return 1;
 else
  return 0;
}

// 역행렬을 구하는 함수 구현
void solveInverse(double **matrix, int size, double **inv){
 for(int i=0; i<size; i++){ // 열의 인덱스
  inv[size-1][i] = matrix[size-1][size+i] / matrix[size-1][size-1];
  for(int j=size-2; j>=0; j--){
   double temp = 0.0;
   for(int k=size-1; k>j; k--){
    temp += (matrix[j][k]*inv[k][i]);
   }
   inv[j][i] = (matrix[j][size+i]-temp) / matrix[j][j];
  }
 }
}

// n x n 크기의 행렬을 저장하기 위한 함수 구현
void enter_nxn_Matrix(double **matrix, int size){
 for(int i=0; i<size; i++){
  cout << i+1 << "행의 값들을 넣어주세요 (예) 2 4 5 3 ... -> ";
  for(int j=0; j<size; j++){
   cin >> matrix[i][j];
  }
 }
 for(i=0; i<size; i++){
  for(int j=size; j<2*size; j++){
   if((i+size) == j)
    matrix[i][j] = 1;
   else
    matrix[i][j] = 0;
  }
 }
}

// 임의 크기의 행렬을 출력하는 함수 구현
void showMatrix(double **matrix, int rowSize, int colSize){
 cout << endl << "< 입력하신 행렬의 역행렬은 다음과 같습니다 >" << endl;
 for(int i=0; i<rowSize; i++){
  cout << endl;
 
  if(i==0) cout << "┏";
  else if(i==rowSize-1) cout << "┗";
  else cout << "┃";

  for(int j=0; j<colSize; j++){
   cout << setw(12) << matrix[i][j];
  }

  if(i==0) cout << " ┓";
  else if(i==rowSize-1) cout << " ┛";
  else cout << " ┃";
 }
 cout << endl << endl;
}

int main(){
 double **matrix, **inv;
 int size;

 cout << "n by n 행렬의 크기 n 값을 넣어주세요 (예) 5 -> ";
 cin >> size;
 
 matrix = new double*[size];
 inv = new double*[size];
 for(int i=0; i < size; i++){
  matrix[i] = new double [size*2];
  inv[i] = new double [size];
 }

 enter_nxn_Matrix(matrix, size);
 //showMatrix(matrix, size, size);
 if(!existINV(matrix, size)){
  cout << endl << "< 역행렬이 존재하지 않는 행렬이므로 프로그램을 종료합니다 >" << endl;
  return 0;
 }
 //showMatrix(matrix, size, 2*size);
 solveInverse(matrix,size,inv);
 showMatrix(inv, size, size);
 return 1;
}

출처 : Tong - 흔하지않은사람님의 c/c++통

'알고리즘 > 이미지 처리' 카테고리의 다른 글

Cubic B-Splines from wikipeda ...  (0) 2008.03.06
B-Spline을 활용하는 이미지 와핑 관련...  (0) 2008.03.06
역행렬 구하기  (0) 2008.03.05
이중선형 필터링  (0) 2008.03.05
Perspective projection matrix  (0) 2008.03.05
다각형을 가져오기 위한 노력...  (0) 2008.03.04

+ Recent posts