[비트마스킹] 개념

10진법

123

3x10^0 + 2x10^1 + 1x10^2

각각의 자리는 0~9로 10개의 숫자로 "표현"된다.

 

 

이진수

0또는 1로 표현하는 "이진법"으로 표현하는 수를 이진수라고 한다.

 

일반적으로 이진법의 수를 십진법의 수와 구별하기 위해 다음과 같은 방법을 쓴다.

(1) 100101b (b를 덧붙이기 b는 binary의 약자)

(2) 100101(2) ((2)를 덧붙임, 주로 수학에서 쓰임)

(3) Ob100101 (앞에 Ob를 덧붙임)

 

오른쪽 끝에서부터 각각의 자리는 1부터 2가 곱해지며 1,2,4,8,16,32 ... 이런식으로 2배씩 증가하게 되며 수를 표현한다.

각각의 자리는 "비트" 라고 할 수 있고, 0인지 1인지를 통해 해당 수 1또는 2,4 등을 더하지 않거나 더하는 걸 기반으로 수를 표현

 

bit = binary Digit의 약자

 

0 -> 비트가 꺼저 있다.

1 -> 비트가 켜져 있다.

 

 

0과 1은

boolean 배열로도 표현할 수 있다.

 

0 -> false

1 -> true

 

비트 연산자의 기초



&	비트단위로 AND 연산을 한다.
|	비트단위로 OR 연산을 한다.
^	비트단위로 XOR 연산을 한다.
~	피연산자의 모든 비트를 반전시킨다.
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다.
>>	피연산자의 비트 열을 오른쪽으로 이동시킨다.

 

 

&, |

& 는 true & true = true ( 1 & 1 = 1 )고 나머지는 모두 false를 반환하는 것이다.

1은 true고, false는 0이다.

 

0 & 0	0
0 & 1	0
1 & 0	0
1 & 1	1

AND 연산자

만약 1001 & 1000을 하면 어떻게 될까?

1000이된다!

 

OR 연산자

| 는 하나라도 true면 모두 true

0|0	0
0|1	1
1|0	1
1|1	1

 

Shift 연산자

 

왼쪽 시프트 연산자 <<

비트를 왼쪽으로 옮긴다. 

a << b 는 a라는 비트를 b만큼 왼쪽으로 옮긴다는 의미이다.

 

a << b = ax2^b

 

오른쪽 시프트 연산자 >>

비트를 오른쪽으로 옮긴다.

a >> b는  a라는 비트를 b만큼 오른쪽으로 옮긴다는 의미이다.

 

a x (1/2)^b

 

^, ~ 연산자

XOR 연산자 ^

true ^ true = false

false ^ false = false

나머지는 다 true를 반환한다.

 

즉, 값이 같은 경우 false를 반환한다.

0^0	0
0^1	1
1^0	1
1^1	0

 

같은것을 싫어행!

 

~

One's completion

 

1의 보수연산자 -> 비트를 반전시킨다.

 

~(value) = -(value + 1)

 

 

 

출처 : https://blog.naver.com/jhc9639/222310927725

[알고리즘 강의] 4주차. 비트마스킹

 

비트연산자 활용법 (암기!)

 

idx번째 비트끄기	s&=~(1<<idx)
idx번째 비트 XOR 연산	S^=(1<<idx)
최하위 켜져있는 비트 찾기	idx = (S & -S)
크기가 n인 집합의 모든 비트를 켜기	(1 << n ) - 1
idx번째 비트를 켜기	S|=(1 << idx)
idx번째 비트가 켜져 있는지 확인하기	if(S&(1<<idx))

 

비트연산자 활용법 #1. idx 번째 비트끄기

비트를 켜다 : 1로만든다.

비트를 끄다 : 0으로 만든다.

 

S& = ~ (1 << idx)

 

비트연산자 활용법 #2. idx 번째 비트 XOR 연산 ( toggle )

S^= (1 << idx)

idx에 존재하는 값을 켜고 기존 값은 꺼준다. (toggle과 같은 기능)

 

비트연산자 활용법 #3. 최하위 켜져있는 비트 찾기

idx = (S & -S)

최하위 켜져있는 비트란?

10010에서 최하위 켜져있는 비트는 10010 

오른쪽에서부터 탐색했을때 가장 1이되는 녀석 = 가장 낮은 녀석

 

비트연산자 활용법 #4. 크기가 n인 집합의 모든 비트를 켜기

(1 << n ) - 1

 

비트연산자 활용법 #5. idx번째 비트를 켜기

S|=(1 << idx)

 

비트연산자 활용법 #6. idx번째 비트가 켜져있는지 확인하기

if(S&(1<<idx))