비트연산 과연 더 빠른가?

비트연산이란?

"한 개 혹은 두 개의 이진수에 대해 비트 단위로 적용되는 연산이다." - 위키백과-

 

비트연산을 사용하는 이유?

컴퓨터가 자료형(int, long double 등등)을 비트로 변환하는 작업을 사용자가 미리 해주기 때문에 빠름

대표적으로 << = *, >> = /이 있음

 

정말로 비트연산이 기본 연산보다 빠른가?

여러 언어들마다 실행시간을 측정할 수 있습니다.

java

곱하기 + 나누기

long beforeTime = System.currentTimeMillis();
		
long n = 1, m = 1;
for(int i = 0; i < 1000000; i++) {
	for(int j = 0; j < 5000; j++) {
		n *= 2;
		m *= 2;
		n /= 2;
		m /= 2;
	}
}
		
long afterTime = System.currentTimeMillis();
		
System.out.print("소요시간 : " + (afterTime - beforeTime) / 1000 + "." + (afterTime - beforeTime) % 1000);

소요시간 : 3.205

long beforeTime = System.currentTimeMillis();
		
long n = 1, m = 1;
for(int i = 0; i < 1000000; i++) {
	for(int j = 0; j < 5000; j++) {
		n = n << 1;
		m = m << 1;
		n = n >> 1;
		m = m >> 1;
	}
}
		
long afterTime = System.currentTimeMillis();
		
System.out.print("소요시간 : " + (afterTime - beforeTime) / 1000 + "." + (afterTime - beforeTime) % 1000);

소요시간 : 0.228

 

이처럼 *와 /기 연산 대신에 <<와 >>을 사용하면 실행 시간을 단축시킬 수 있음.

 

예시는 overflow가 되어 0이 되게 하지 않기 위해 *와 /연산을 사용하여 원래 값을 유지하면서 시간을 측정했습니다.

 

 

두 수의 평균 구하기

두 수의 평균 구하는 방식은 (a + b) / 2가 있습니다.

비트연산으로는 (a & b) + ((a ^ b) >> 1)와 ((a | b) + (a & b)) >> 1 가 있습니다..

((a | b) + (a & b)) >> 1같은 경우에는 ((a | b) + (a & b))를 할 경우, Overflow가 발생할 수 있습니다.

그러나 (a & b) + ((a ^ b) >> 1)이거 같은 경우에는 Overflow를 걱정하지 않아도 됩니다.

 

그 이유는 "더하고 나눈다" vs "각각 구하고 더한다" 입니다.

더하고 나눌 경우, "더한 경우"에 overflow가 발생하여 값이 달라질 수 있습니다.

 

long beforeTime = System.currentTimeMillis();
		
long a = 2, b = 3;
		
for(int i = 0; i < 1000000; i++) {
	for(int j = 0; j < 5000; j++) {
		a = (a + b) / 2;
	}
}
		
long afterTime = System.currentTimeMillis();
		
System.out.print("소요시간 : " + (afterTime - beforeTime) / 1000 + "." + (afterTime - beforeTime) % 1000);

소요시간 : 4.335

long beforeTime = System.currentTimeMillis();
		
long a = 2, b = 3;
		
for(int i = 0; i < 1000000; i++) {
	for(int j = 0; j < 5000; j++) {
		a = ((a | b) + (a & b)) >> 1;
	}
}
		
long afterTime = System.currentTimeMillis();
		
System.out.print("소요시간 : " + (afterTime - beforeTime) / 1000 + "." + (afterTime - beforeTime) % 1000);

소요시간 : 3.306

long beforeTime = System.currentTimeMillis();
		
long a = 2, b = 3;
		
for(int i = 0; i < 1000000; i++) {
	for(int j = 0; j < 5000; j++) {
		a = (a&b) + (a^b)>>1;
	}
}
		
long afterTime = System.currentTimeMillis();
		
System.out.print("소요시간 : " + (afterTime - beforeTime) / 1000 + "." + (afterTime - beforeTime) % 1000);

소요시간 : 3.297

 

평균 구하는 방식을 비트연산으로 측정해봤습니다.

별로 차이가 안나는거 같아 보이지만, 이러한 활동을 여러번 하다보면, 시간이 더욱 소모가 될 것입니다.

 

많은 비트연산 소스들을 보고 싶으신 분들은

https://github.com/dalihub/dali-adaptor/blob/master/dali/internal/imaging/common/image-operations.h#L600

GitHub - dalihub/dali-adaptor: Provides integration with the native application framework and windowing system. Platform impleme

요기를 보시면 될거 같습니다.