유용한 C program

1. 제일 오른쪽에 있는 '1'의 위치 구하기

rightBit = bitf ^ (bitf & (bitf - 1));



00010000b - 00000001b = 00001111b 라는 숫자의 기본 개념과 &, ^ 연산의 오묘함을 이용한 것이다.

실제로 아무 숫자나 넣어서 해보면 금방 이해할 수 있다.

최상위 비트도 이처럼 간단하게 구할 수 없을까? 해서 이렇게 저렇게 생각해 봤지만 현재로선 모르겠다.

추가사항: 2의 보수 아키텍처를 사용한다면 더욱 간편하고 빠른 식을 사용할 수 있다.
rightBit = -bitf & bitf;
결과값에 영향은 없으나 bitf가 unsigned형일 경우 컴파일 시 경고가 나타난다.
따라서 아래와 같이 수정한다.
rightBit = -(signed)bitf & bitf;

예) 40, -40
40 = 00101000, -40=11011000
따라서 결과값은 8




2. 주어진 수가 2의 제곱수(1, 2, 4, 8, 16 등등)인지 검사하기(출처: flipCode)

inline bool isPowOf2(int value) {   return !(value & (value - 1));   }


최하위 비트 구하기와 비슷한 원리다.

다른 버전(출처: java api)
inline bool isPowOf2(int value) {   return (value & -value) == value;   }



3. 임시 변수없는 SWAP 매크로(출처: Graphics Gems)

#define SWAP(a, b) ((a)^=(b)^=(a)^=(b))



위의 매크로는 정수형 타입에만 해당되는 연산이다.

부동소수일 경우엔 그냥 std::swap()을 사용해라.

템플릿 함수를 만들어 봤는데 알고보니 이미 std::swap()라는 게 제공되고 있더라.

매크로를 함수화해서 사용하는 건 보통의 함수 호출만큼 안전하지 않다.

예를들면, 아래의 경우



int a = 6, b = 9;

SWAP(++a, ++b);



a=10, b=7이 아니라 a=11, b=8이 된다. 왜 그런지는 말 안해도 알 것이라 믿는다.

그렇다고 함수화하는 건 속도 면에서 매크로보다 메리트가 떨어진다.

그래서 이를 사용할 때는 이것은 매크로이므로 복잡한 연산과 함께하지 말고 단순하게 사용하라는 걸 경각시키기 위해서 함수와는 달리 이름을 대문자로 하였다. (사실 이런 이유 등으로 매크로는 대개 대문자로 하는 거 같다.)

아, 그리고 a와 b의 어드레스가 같다면 결과는 무조건 0이 된다.



4. 0이 아닌 비트들의 개수 세기(예를 들어 0xf0는 4개)(출처: flipCode)



8비트용:



v = (v & 0x55) + ((v >> 1) & 0x55);

v = (v & 0x33) + ((v >> 2) & 0x33);

return (v & 0x0f) + ((v >> 4) & 0x0f);



참고로 0x55 = 01010101b, 0x33 = 00110011b, 0x0F = 00001111b



32비트용:



#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001

#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111



v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);

v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);

return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f;



8비트는 그럭저럭 봐줄만해도 32비트의 복잡도는... 제길

그래서 8비트에서의 원리를 이용해 32비트 짜리를 한 번 만들어 보았다.

성능이야 위에 거보단 떨어지겠지만 이해하기 쉽고 64비트로의 확장 또한 용이하다.



int cntBit32(long value)

{

    value = (value & 0x55555555) + ((value >>  1) & 0x55555555);

    value = (value & 0x33333333) + ((value >>  2) & 0x33333333);

    value = (value & 0x0F0F0F0F) + ((value >>  4) & 0x0F0F0F0F);

    value = (value & 0x00FF00FF) + ((value >>  8) & 0x00FF00FF);

    return   (value & 0x0000FFFF) + ((value >> 16) & 0x0000FFFF);

}



굳이 연산을 이해하지 않아도 누구라도 확장된 버전을 만들 수 있을거라 생각한다.





5.32비트 색상 두 개의 50% 혼합(출처: flipCode)

32비트 AARRGGBB 형식의 색상들을 1:1로 혼합...



알파채널이 있는 경우

color = ((color & 0xfefefefe) >> 1) + ((backColor & 0xfefefefe) >> 1)

            + ((color | backColor) & 0x01010101);



알파 채널 안쓰는 경우

color = ((color & 0x00fefefe >> 1) + (backColor & 0x00fefefe) >> 1)

            + ((color | backColor) & 0x00010101);



그래픽쪽은 잘 모르더라도 비트 연산은  어느 정도 이해 가능했다.

(color & 0xfefefefe) >> 1 은 각 ARGB의 값을 2로 나눈 것이다.

하지만 왜 굳이 ((color | backColor) & 0x01010101) 연산을 해서 각 ARGB값에 0이나 1을 더했는지는 모르겠다. 그리고 출처에는 알파 채널 안쓰는 경우

color = ((ccolor & 0x00fefefe) + (backColor & 0x00fefefe) >> 1)

            + ((color | backColor) & 0x00010101);

라고 나와 있지만 아무래도 오타인 거 같다.

추가.
1. 간단한 홀짝 판정
int odd = num & 1;  // 짝수면 0, 홀수면 1이 된다.

2. n개의 1로 채우기. mask에 유용하다.
int mask = (1 << n) - 1;  // n=4이면 1이 다음과 같이 변한다. 00000001 => 00010000 => 00001111
혹은 int mask = ~(~0 << n);

3. n개의 0으로 채우기. 위에꺼 응용
int mask = ~(1 << n) + 1; // n = 4이면 1이 다음과 같이 변한다. 00000001 => 00010000 => 11101111 => 11110000
혹은 int mask = ~0 << n;

4. 비트 뒤집기(리눅스에서는 이렇게 한단다)
x = (x >> 4) | (x << 4);
x = (x >> 2 & 0x33) | (x << 2 & 0xcc);
x = (x >> 1 & 0x55) | (x << 1 & 0xaa);

5. 비트 연산들이 잘 나와있는 곳
http://graphics.stanford.edu/~seander/bithacks.html
http://www.hackersdelight.org/
left most bit detection 으로 구글링하다 발견했다. 최고다. 역시 스탠포드 킹왕짱