알고리즘에서 쓰는 비트연산

자주 쓰는 비트연산 정리 (feat. 펜윅트리)

 

(1<<n) : n번째 비트 1로(원소 추가)

1을 n번 이동했으니까 n번째 비트가 1이 됨

number |= (1<<n);

 

(1<<n)-1 : n개의 비트 모두 1로

1을 빼면 모든 비트가 1이 된다

그 수랑 or연산을 하면 모든 비트를 1로 만들 수 있다

number |= (1<<n)-1;

 

(number & (1<<n) ) > 0 ? true:false; : n번째 비트가 1인가?

number 위치에 비트가 켜져있으면 AND연산 뒤에도 1로 남아있다

그러면 값은 0보다 클 것이고, 0이었다면 0이 되면서 false를 반환한다

bool isTrue;

isTrue = (number & (1<<n)) > 0 ? true:false;

 

number ^= (1<<n) : n번째 비트 반전

원래 비트가 1이었다면 XOR 뒤에는 0이되고, 0이었다면 1이 됨

 

number &= ~(1<<x) : n번째 비트 0으로(원소 삭제)

(1<<x)를 not하면 0이 되고

원래 number와 &해주면 0과의 AND연산으로 0이 된다

 

n & (n-1) == 0 : 정수의 2의 지수승 여부 확인

2^n형태라면 1<<n 연산과 같기 때문에 가능한 방법

예) 1000 & 111 = 0000

return n & (n-1) == 0;

 

n & -n : n을 이진수로 했을 때 마지막 1의 위치 찾기

펜윅트리에서 씀

n -= n & -n : 마지막 1값을 뺀다

n += n & -n: 마지막 1값을 더한다

 

참고로 ~i가 반전이고 -i는 ~i+1 이다 (2의 보수법 때문에 +1)