비트 연산은 우선순위가 낮은 편이기 때문에 원하는 위치에 괄호를 작성하여 정확하게 계산할 수 있도록 하는게 중요하다.



C++에서 1은 부호있는 32비트 상수이기  때문에, 64비트를 사용할 때에는 1뒤에 ull을 붙여줘야 제대로 인식한다.


unsigned long long bit = (1ull<<40)-1; (O) -> 1099511627775


unsigned long long bit = (1<<40)-1; (X) -> 18446744073709551615



공집합( 모든 비트가 0)

unsigned int bit = 0;


꽉찬 집합(모든 비트가 1)


unsigned int bit = (1<<n) - 1;


사용할 비트 수만큼 왼쪽으로 시프트한 다음 1을 빼면 된다.


unsigned int bit = (1<<32) - 1; -> 1111 1111 1111 1111 1111 1111 1111 1111



기존 비트에서 원하는 비트의 위치를 1로 바꾸기

비트를 1로 바꿀 만큼 왼쪽으로 시프트 시킨 후 , or연산을 한다.

bit |= (1<<n);



특정 비트가 1인지 확인하기

if(bit & (1<<n)) -> 특정 비트가 1이면 1<<n 반환, 0이면 0 반환



기존 비트에서 원하는 비트의 위치를 0으로 바꾸기

bit &= ~(1<<n);


n번째 비트가 0이면 1로, 1이면 0으로 바꾸기

bit ^= (1<<n); -> xor 연산을 하면 가능하다.



비트에서 1의 개수 세기

1
2
3
4
5
6
int bitCount(int x)
{
    if (x == 0)
        return 0;
    return x % 2 + bitCount(x / 2);
}
cs



처음 1인 비트 찾기

int first = ( bit & -bit);

2^n의 값이 반환된다.

즉 10진수 240 은 1111 0000로, 처음 1은 4번째 비트에서 나타난다. 그러면 위 식에 의해 2^4 = 16의 값을 가지게 된다.


처음 1인 비트를 0으로 바꾸기


bit &= (bit -1);



모든 부분집합 탐색

처음 시작은 모든 비트가 1로 채워져있어야 한다.


1
2
3
4
for (int subset = a; subset; subset = ((subset - 1) & a))
    {
        
    }
cs



참고문헌: 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략

'컴퓨터공학 > 알고리즘' 카테고리의 다른 글

이진 탐색(Binary Search)  (0) 2018.08.08

이진 탐색 알고리즘은 정렬된 배열에서만 사용 가능하다.


아주 많은 데이터가 저장되어 있는 배열에서 순차탐색보다 효과적으로 값을 찾을 수 있다.


기본 원리는 배열에서 중간 위치를 기준으로  찾고자 하는 값이 더 작으면 중간 위치의 왼쪽에서 계속 탐색,

찾고자 하는 값이 더 크면 중간 위치보다 오른쪽에 있는 값들을 탐색하며,


다음 위치는 계속 남은 배열의 중간위치를 기준으로 탐색한다.



위 그림의 예시에서 1부터 10까지 저장된 배열에서 2를 찾을 것이다.


초기값으로 front = 0, rear = 9가 되며, mid = (0 + 9 ) / 2 = 4 를 가진다.


mid인덱스에서 가지고 있는 값은 5이므로, 찾고자 하는 숫자가 더 작다. 


그러므로 rear의 값을 mid - 1로 바꿔서 다시 탐색한다.


그러면 front = 0, rear = 3, mid = 1이 된다.


1번 인덱스는 2이므로, 찾고자하는 숫자와 일치하므로 이진 탐색을 종료한다.



반복문을 사용하는 방법과, 재귀호출을 통한 구현이 모두 가능하다.

일반적으로는 반복문을 사용해서 구현하면 된다.


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
//Binary Search
#include <stdio.h>
 
int binarySearchRecursion(int number[], int front, int rear, int target)
{
    int mid = (front + rear) / 2;
 
    if (front > rear)//배열에서 탐색하지 못함
    {
        return -1;
    }
 
    if (number[mid] == target)//찾은 경우
    {
        return mid;
    }
    else if (number[mid] < target)//찾고자 하는 값이 더 크므로 오른쪽 탐색
    {
        return binarySearchRecursion(number, mid + 1, rear, target);
    }
    else//찾고자 하는 값이 더 작으므로 왼쪽 탐색
    {
        return binarySearchRecursion(number, front, mid - 1, target);
    }
}
 
int binarySearchIteration(int number[], int size, int target)
{
    int front = 0;
    int rear = size-1;
    int mid;
 
    while (front <= rear)
    {
        mid = (front + rear) / 2;
        if (number[mid] == target)//찾은 경우
        {
            return mid;
        }
 
        if (number[mid] < target)
        {//찾는 값이 더 크므로 mid를 기준으로 오른쪽 탐색
            front = mid + 1;
        }
        else // if(number[mid] > target)
        {//찾는 값이 더 작으므로 mide를 기준으로 왼쪽 탐색
            rear = mid - 1;
        }
    }
    //찾지 못하고 while문이 종료되면 실패 반환
    return -1;
}
 
int main(void)
{
    int number[200];
 
    for (int i = 0; i < 200; i++)
        number[i] = i + 1;
 
    int findNum = 201;
 
    printf("Binary Search Iterative\n");
    int index = binarySearchIteration(number, sizeof(number) / sizeof(int), findNum);
    if(index!=-1)
        printf("NUM : %d = %d index\n", findNum, index);
    else
        printf("NUM : %d is not exist\n", findNum);
 
    printf("Binary Search Recursive\n");
    index = binarySearchRecursion(number, 0, (sizeof(number) / sizeof(int)) - 1, findNum);
    if (index != -1)
        printf("NUM : %d = %d index\n", findNum, index);
    else
        printf("NUM : %d is not exist\n", findNum);
 
    return 0;
}
cs


'컴퓨터공학 > 알고리즘' 카테고리의 다른 글

비트연산  (0) 2018.08.10

+ Recent posts

티스토리툴바