×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,238,771명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

비트 연산자( AND &, OR |, XOR ^, SHIFT <<, >>)에 대한 내용 및


이 비트 연산자를 이용하여 비트 연산을 응용하는 방법을 설명해 두었고,


중요한 내용은 [중요]라고 표기해 두었습니다.


모든 내용은 소스 코드에 수록되어있고, 소스 코드에 주석과 함께 설명을 달아두었습니다.


소스 코드 아래에는 스크린샷을 통해 출력 화면을 확인 할 수 있습니다.





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <iostream>
#include <cstdio>
#include <math.h>
 
using namespace std;
 
int main()
{
    int val;
    
    // AND 연산 (&)
    val = 754 & 470;
    
    cout << "AND 연산 (&)\n" << endl;
    cout << "754의 bit 값 :: " << "0010 1111 0010" << endl;
    cout << "470의 bit 값 :: " << "0001 1101 0110" << endl;
 
    cout << "754 & 470 값 :: " << "0000 1101 0010 :: " << val << endl;
    cout << endl;
 
    // OR 연산 (|)
    val = 754 | 470;
 
    cout << "OR 연산 (|)\n" << endl;
    cout << "754의 bit 값 :: " << "0010 1111 0010" << endl;
    cout << "470의 bit 값 :: " << "0001 1101 0110" << endl;
 
    cout << "754 | 470 값 :: " << "0011 1111 0110 :: " << val << endl;
    cout << endl;
    
    // XOR 연산 (^)
    val = 754 470;
 
    cout << "XOR 연산 (^)\n" << endl;
    cout << "754의 bit 값 :: " << "0010 1111 0010" << endl;
    cout << "470의 bit 값 :: " << "0001 1101 0110" << endl;
 
    cout << "754 ^ 470 값 :: " << "0011 0010 0100 :: " << val << endl;
    cout << endl;
 
    // 좌측 쉬프트 연산 (<<)
    val = 1234 << 1;
 
    cout << "좌측 쉬프트 연산 (<<)\n" << endl;
    cout << "1234 bit 값 :: " << "0100 1101 0010" << endl;
    cout << "1234 << 1 값 :: " << "1001 1010 0100 :: " << val << endl;
    cout << endl;
 
    // 우측 쉬프트 연산 (>>)
    val = 2468 >> 1;
 
    cout << "우측 쉬프트 연산 (>>)\n" << endl;
    cout << "2468 bit 값 :: " << "1001 1010 0100" << endl;
    cout << "2468 >> 1 값 :: " << "0100 1101 0010 :: " << val << endl;
    cout << endl;
 
    cout << "* 즉, 좌측 쉬프트 연산을 하게 되면 <현재값 * 2>를 할 수 있고, *" << endl;
    cout << "*    우측 쉬프트 연산을 하게 되면 <현재값 / 2>를 할 수 있다. *" << endl;
    cout << endl;
 
    // 비트 연산 시 주의 사항
    val = (& == 4);
    cout << "비트 연산 시 주의 사항\n" << endl;
 
    cout << "6 & 4 값 :: :: " << "0100" << endl;
    cout << "6 & 4 == 4 값 :: " << val << endl;
 
    val = ((& 4== 4);
    cout << "(6 & 4) == 4 값 :: \n" << val << endl;
    
    cout << "* 즉, bit 연산이 우선순위가 높다 해도 더 높은 우선순위 연산자가 있기에 *" << endl;
    cout << "*   bit 연산 시에는 항상 괄호를 습관화 한다." << endl;
    cout << endl;
 
    // 쉬프트 연산 시 주의 사항
    long long int ex1, ex2;
 
    ex1 = << 30;
    cout << "1 << 30 :: " << ex1 << endl;
 
    ex1 = << 32;
    cout << "1 << 31 :: " << ex1 << endl;
    cout << endl;
    
    ex2 = 1ull << 30;
    cout << "1ull << 30 :: " << ex2 << endl;
 
    ex2 = 1ull << 62;
    cout << "1ull << 31 :: " << ex2 << endl;
    cout << endl;
 
    cout << "* 즉, C++에서 1은 부호 있는 32비트 상수로 취급 되기 때문에" << endl;
    cout << "<< x에서 x값이 32 이상이면 오버 플로우가 발생한다.\n" << endl;
    cout << "따라서 경우에 따라 ull을 이용하여 부호 없는 상수로 취급하도록 만들어 주어야 한다." << endl;
    cout << endl;
 
    // 집합의 표현
    cout << "집합의 표현 \n" << endl;
    cout << "집합 A :: {1, 4, 16, 64}" << endl;
    cout << "집합 B :: {2, 8, 32, 128}" << endl;
    cout << endl;
 
    int A = 0, B = 0;
 
    // 0000 0000비트에 합집합 |= 방식을 이용하여 집합을 생성
    for (int i = 0; i < 4; i++)
    {
        A |= (<< (i * 2));
        B |= (<< ((i * 2+ 1));
    }
    cout << "현재 A :: 0101 0101" << endl;
    cout << "현재 B :: 1010 1010" << endl;
 
    cout << "A :: " << A << " B :: " << B << endl;
    cout << endl;
    
    // 집합의 확인은 & 기호를 이용하여 확인 할 수 있다.
    cout << "집합 A의 원소 나열 :: ";
    for (int i = 0; i < 8; i++)
        if (A & (<< i))
            cout << pow(2,i) << " ";
 
    cout << endl;
    cout << "집합 B의 원소 나열 :: ";
    for (int i = 0; i < 8; i++)
        if (B & (<< i))
            cout << pow(2, i) << " ";
 
    cout << "\n" << endl;
 
    // 전체 집합 만들기
    int C = 0;
 
    cout << "집합 C로 1111 1111 만들기" << endl;
    C = (<< 8- 1;
 
    cout << "집합 C의 원소 나열 :: ";
    for (int i = 0; i < 8; i++)
        if (C & (<< i))
            cout << pow(2, i) << " ";
 
    cout << "\n" << endl;
 
    // 원소의 삭제
    C -= << 3;
 
    cout << "원소의 삭제를 통한 집합 C의 원소 나열 :: ";
    for (int i = 0; i < 8; i++)
        if (C & (<< i))
            cout << pow(2, i) << " ";
 
    cout << "\n" << endl;
 
    // 원소의 토글 (XOR 이용)
 
    for(int i = ; i < ; i ++)
    C ^= << i;
 
    cout << "토글된 집합 C의 원소 나열 :: ";
    for (int i = 0; i < 8; i++)
        if (C & (<< i))
            cout << pow(2, i) << " ";
 
    cout << "\n" << endl;
 
    // 집합 크기 구하기
    int cnt = 0;
    for (int i = 0; i < 8; i++)
        if (C & (<< i))
            cnt++;
 
    cout << "집합 C의 크기 :: " << cnt << endl;
 
    // [중요] 최하위 비트 구하기(펜윅 트리에 이용)
    
    /*
        :: 원리 :: 
        1100이 있다고 생각하자 1100의 2의 보수는 0011에서 + 1을 한 0100이다,
        결국 1100은 val이고 0100은 -val이다.
        이 두개를 & 연산을 하게 된다면 0100이 되는데 이때 1은 최하위 비트 위치를 의미하고 있다.
        위의 예시를 이용하여 일반적인 식을 도출하면 (val & -val)을 이용하면 최하위 비트를 구할 수 있다. 
    */
    val = 12// 1100
    int first = (val & -val);
 
    cout << "최하위 비트 값 :: " << first << endl;
    cout << endl;
 
    // [중요] 최소 원소(최하위 비트) 지우기
 
    /*
        :: 원리 ::
        예를 들어보자.
        40이라는 값이 있다. 이 값의 비트는 0010 1000이다.
        이때 val - 1은 39 즉, 이 값의 비트는 0010 0111이다.
        그럼 val & val - 1은 0010 0000이다.
        
        즉, 값 - 1을 하게 되면 최하위 비트가 0이되고 그 뒤로는 모두 1이 되는데,
        이 값을 &연산을 하게 된다면 최하위 비트부터 모두 0이된다.
    */
 
    val = 12// 1100
    cout << "현재 값 :: " << val << endl;\
 
    val &= val - 1;
    cout << "최소 원소(최하위 비트)를 지운 값 :: " << val << endl;
 
    cout << endl;
 
    // [중요] 모든 부분 집합 순회하기
    
    // 위의 방식을 이용하여 모든 부분 집합을 나열 할 수 있다.
    val = 12;
 
    cout << "집합 val의 원소 나열 :: ";
    for (int i = 0; i < 8; i++)
        if (val & (<< i))
            cout << pow(2, i) << " ";
 
    cout << "\n" << endl;
 
    cout << "집합 val의 모든 부분 집합 나열 ::";
    for(int subset = val; subset; subset = ((subset - 1& val))
        cout << subset << " ";
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus








반응형