[개념] Bit연산

비트연산

 

logical right shift

 

 

 

arithmetic right shift

- 부호를 염두해두고 하는 shift 연산자

 

 

① getBit

bit연산자를 이용해 숫자 9의 이진수 값에서,  i=(3)번 인덱스 값을 가져오려면? 

 

 

 

9의 경우 3번 인덱스의 값이 1이다. (01001)

20의 경우 3번 인덱스의 값이 0이다  (10100)

우리가 원하는건 해당 자리수의 값이므로, 

나머지 자리들은 다 0으로 만들어주고 해당 자리수만 원본데이터에서 가져오는 값을 만들어줘야 한다.

 

 

그렇게 구하기 위해서는 해당 인덱스의 값을 1로 세팅하고 나머지는 0으로 세팅하여 -> 1000

& 연산자를 해주면 원하는 값을 얻을 수 있다. = X

 

 

그러면 연산할 값인 1000은 어떻게 만들어낼까?

1을 i만큼 왼쪽으로 shift하면 1000 을 만들어낼 수 있다.

다음과 같이 해당 index값만 1이고 나머지는 0인 수를 만들어낼 수 있다.

 

 

9의 이진수 1001과 1000을 & 해준다.

 

 

주어진 값이 5인 경우는 이진수가 0101 이다.

-> 3번 index의 bit값이 0

연산 결과값 0000

결과가 0일때는 false, 0이 아닐때는 true를 반환하면 

해당 index의  bit값이 0인지 1인지를 알아내는 함수를 만들 수 있다.

 

 

public class Test {
	static boolean getBit(int num, int i) {
		// 해당 index의 bit가 1이면 true, 0이면 false를 반환
		return (num & (1<<i)) != 0; 
	}
	public static void main(String[] args) {
		// 1 0 0 1
		System.out.println(getBit(9,3));
		// 0 1 0 1
		System.out.println(getBit(5,3));
	}
}

 

결과값

 

 

② setBit 

원하는 index에 1로 값을 세팅하려면?

 

1을 i만큼 왼쪽으로 shift 해서 1000 을 만들어낸다.

이것을 본래의 수 9 ( 1001 ) 과 | (or) 연산을 시킨다.

 

 

public class Test {
	static int setBit(int num, int i) {
		// 해당 index의 bit가 1이면 true, 0이면 false를 반환
		return num | (1<<i);
	}
	public static void main(String[] args) {
		// 숫자 5에 3번째 index를 1로 세팅해보자
		// 0 1 0 1 -> 1 1 0 1 로
		System.out.println(setBit(5,3));
	}
}

 

결과로 13이 나온다.

 

③ clearBit

해당 index를 무조건 0으로 세팅하려면?

 

해당 index만 0이고 나머지 숫자들은 1인  0 1 1 1 과 &연산자를 해주면 된다.

-> 0 1 1 1 은 어떻게 만들까?

먼저 left shift를 통해 1 0 0 0 을 만들고

앞에 not을 붙여 bit를 정 반대로 바꿔준다.

0 1 1 1 = ~ 1 0 0 0

-> 그 다음 이걸 원본값과 & 연산자 해주면 해당 bit가 clear된다.

 

 

 

public class Test {
	static int clearBit(int num, int i) {
		return num & ~(1<<i);
	}
	public static void main(String[] args) {
		// 1 0 0 1 -> 0 0 0 1
		System.out.println(clearBit(9,3));
	}
}

 

결과값 : 1

 

 

 

---

 

백준 1648. 격자판 채우기

문제 보러가기 

 

문제

세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노를 이용해서 빈 공간이 없도록 채우는 방법의 수는 몇일까? 아래 그림은 N = 3, M = 6인 예이다.

 

 

 

입력

첫째 줄에 격자판의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 14)

 

출력

첫째 줄에 주어진 격자판을 2x1크기의 도미노로 빈 공간이 없도록 채우는 방법의 수를 9901로 나눈 나머지를 출력한다.

 

 

칸에 1을 넣어 넣었다는 표시를 해준다.

#include <iostream>
#include <cstring>

using namespace std; 

const int MAX = 14;
const int MOD = 9901;

int N, M;
int D[MAX*MAX][1 << MAX];
//  D[i][bit] : i-1 번 타일까지 채워져있고, i번으로부터 M개의 타일의 상태가 bit인 경우의 수 
// ex. D[7][5] : 7번째 칸부터 M개의 칸이 상태가 5이다. ( 5 = 0 0 0 1 0 1 (2) ) 

int tiling(int i, int bit) {

        //전부 채워졌다면 결과에 1을 더해준다.
        if (i == N * M && bit == 0)
                 return 1;

        //마지막 칸까지 갔는데 다 채워지지 않은 경우 실패니깐 0을 반환
        if (i >= N * M)
                 return 0;       
		
        // D[i][bit] : i-1 번 타일까지 채워져있고,
        // i번부터 M개의 타일의 상태가 bit인 경우의 수 
        int &result = D[i][bit];		
        if (result != -1)
                 return result;
                 
        result = 0;

        // i번째가 이미 채워져 있어서 칸을 채울 수 없는 경우
        // 다음 칸을 채워야 함
        // bit를 오른쪽으로 한비트 쉬프트
        if (bit & 1)
            	  result = tiling(i + 1, (bit >> 1));
        //해당 칸이 칠해져있지 않다면 채워야함
        else {
        		//해당 칸은 현재 위치에서 항상 좌상단이라고 가정하고 푼다
                 //2 * 1           
                 result = tiling(i + 1, (bit >> 1) | (1 << (M - 1)));

                 //1 * 2
                 //M - 1번째 타일에 위치하지 않았고 (이럴 경우 1 * 2를 놓을 수 없으니깐) 
                 //다음칸도 비어있을 경우
                 if ((i % M) != (M - 1) && (bit & 2) == 0)
                         result += tiling(i + 2, bit >> 2);
        }
        return result %= MOD;
} 

int main(void)
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        cin >> N >> M; // N x M 칸

        memset(D, -1, sizeof(D));
        cout << tiling(0, 0) << "\n";

        return 0;
}

 

 

 

 

 

 

출처

https://www.youtube.com/watch?v=yHBYeguDR0A&t=744s 

https://jaimemin.tistory.com/1123