비트 연산으로 홀수 짝수 구분하기

n & 1

입력 숫자 n에서 홀수, 짝수를 결정 하는 것은 마지막 자리 숫자이기 때문에 
위 연산의 결과가 1이면 홀수, 0이면 짝수 이다.

ex 1)

10 이라는 10진수 정수를 예로 들면

10은 2진수로 표현하면 1010 이고,

10 & 1 은 1010 & 1과 동일함.

그럼 1010의 마지막 자리는 0 이고, 0과 1을 & 연산 하면 0 이기 때문에

짝수가 된다.

ex 2)
11은 2진수로 1011이고,
11 & 1 는 1011 & 1 와 동일하고

마지막 자리수는 1이기 때문에 1 & 1 = 1 이기 때문에 홀수 이다.

ex 3)
45라면 2진수로 101101 이기 때문에
45 & 1 은  1 & 1이 되기 때문에 결과는 0으로 홀수 가 된다.

정리)

10 == 1010

1010 & 1 == 0

11 == 1011,

1011 & 1 == 1

45 == 101101
101101 & 1 == 0

[Algorithm] Binary Counting - 비트연산을 통한 순열(부분집합, power set) 구하기

프로그래밍을 하다보면, 모든 경우의 수를 확인해야 하는 경우가 생기는데,
이럴경우 각 원소에 대한 모든 부분집합을 구해서 확인해야 한다.

1, 2, 3에 대해서 본다면 아래와 같은 모든 부분 집합이 존재 한다.
(1), (2), (3), (1 2), (1 3), (2 3), (1 2 3)

이러한 부분집합을 구할때 간단히 비트연산을 이용해서 구할 수 있는 방법이 있다.

A, B, C, D에 대한 부분 집합 

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void main(void){     int i, j;     char arr[4] = { 'a', 'b', 'c', 'd' };     int n = 4;     for (i = 0; i < (1 << (n)); i++){         for (j = 0; j < n; j++){             if (i & (1 << j)){                 printf("%c ", arr[j]);             }         }         printf("\n");     } } Colored by Color Scripter

cs

위 비트연산 1<<(n) 과, i & (1<<j) 에 대한 설명은 ->여기로<-

원소 수에 해당하는 N개의 비트열을 이용한다.

N번째 비트값이 1이면 N번째 원소가 포함되었음을 의미한다.

4비트에서 하나씩 증가 했을때의 자리수로 아래와 같이 출력됨.

10 진수	이진수	{A, B, C, D}
0	0000
1	0001	A
2	0010	B
3	0011	B, A
4	0100	C
5	0101	C, A
6	0110	C, B
7	0111	C, B, A
8	1000	D
9	1001	D, A
10	1010	D, B
11	1011	D, B, A
12	1100	D, C
13	1101	D, C, A
14	1110	D, C, B
15	1111	D, C, B, A

[Basic Skill] 유용한 비트 연산자

1<<n

• 2n의 값을 갖는다.
• 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.
• Power set(모든 부분 집합)
• 공집합과 자기 자신을 포함한 모든 부분집합
• 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.

i & (1 << j)

• 계산 결과는 i의 j번째 비트가 1인지 아닌지를 의미한다.