[leetCode] D-13~14. Bit Manipulation, Hamming Weight

AND 비트연산(&)

비트 연산자 &은 비트의 논리곱을 하는 연산자이다.
2개의 피연산자의 각 자리마다 대응하는 비트가 모두 1일 경우 1을 반환한다.

피연산자는 32비트 정수로 변환되며 일련의 비트 0과1로 표현된다.

비트

이진법으로 0과1로 표현한 수

연산자

& : 비트의 논리곱 연산자

이진법으로 나타낸 두 피연산자의 교집합을 반환한다.
a & b

• a = 5 => 101
• b = 3 => 011

101,011중 각 자리에서 마지막 자리에 공통으로 1이 있으므로 1을 반환한다.

| : 비트의 논리합 연산자

이진법으로 나타닌 두 피연산자의 합집합을 반환한다.
a | b

• a = 5 => 101
• b = 3 => 011

같은 자리에 0과1이 있다면 1로 합치기 때문에 111 => 7을 반환한다.

^ : 비트의 배타적 논리합 연산자

이진법으로 나타낸 두 피연산자의 배타적 합집합을 반환한다.
a | b

• a = 5 => 101
• b = 3 => 011

^는 a와 b의 같은 자리의 수가 0혹은 1일 경우 0을 반환하고, 0,1 혹은 1,0일 경우 1을 반환한다.
쉽게 말해, 각 자리의 수가 같으면 0을, 다르면 1을 반환한다.

a와 b의 각 자릿수를 앞부터 비교해보면,
1,0 =>1
0,1 =>1
1,1 =>0

110 => 6을 반환한다.

~ : 비트의 부정연산자 (XOR)

현재 값을 이진수 비트로 변환한 뒤 0은 1로, 1은 0으로 변환한다.

console.log(~5) // -5

console.log(~-5) // 4

>> : 시프트 연산자

<<과 >> 두 개의 연산자가 있다.
a<<b는 a를 b만큼 왼쪽으로 이동시키는 것이다.

5 => 101

5 << 3 = 101000

오른쪽으로 시프트 하는 것도 마찬가지다.

10 => 1010
1010 >> 3 = 0001

비트의 위치가 해당 숫자의 길이를 벗어날 경우,
즉 최대값 또는 최소값의 위치 이상으로 시프트할 경우 자동으로 버려진다.

Hamming Weight

Data에서 1의 갯수를 세는 알고리즘이다.
여기에는 다양한 알고리즘이 있다.

관련 문제 풀이

🔆 D-13

• [leetCode][JS] 191. Number of 1 Bits
• [leetCode][JS] 231. Power of Two

🔆 D-14

• [leetCode][JS] 136. Single Number - 자세한 풀이/설명/그림
• [leetCode][JS] 190. Reverse Bits

Reference

• https://blankspace-dev.tistory.com/425
• http://shumin.co.kr/algorithm-hamming-weight-bit-count/