[알고리즘] 비트 조작하기

NOT
- NOT 연산은 각 자릿수의 값을 반대로 바꾸는 연산이다.
- NOT 0111 = 1000
- x = ~y;
OR
- OR 연산은 두 값의 각 자릿수를 비교해, 둘 중 하나라도 1이 있다면 1을, 아니면 0을 계산한다.
- 0101 OR 0011 = 0111
- x = y | z;
XOR
- XOR 연산은 두 값의 각 자릿수를 비교해,값이 0으로 같으면 0, 값이 1로 같으면 0, 다르면 1을 계산한다.
- 0101 XOR 0011 = 0110
- x = y ^ z;
AND
- AND 연산은 두 값의 각 자릿수를 비교해, 두 값 모두에 1이 있을 때에만 1을, 나머지 경우에는 0을 계산한다.
- 0101 AND 0011 = 0001
- x = y & z;

0110 + 0110 = 1100
- 0110 ＊ 2와 같다 = (0110 « 1)
- 0110을 왼쪽으로 한 번 시프트
- 같은 값을 더하는 것은 왼쪽으로 한 번 시프트하는 것과 같다.
0100 ＊ 0011 = 1100
- 0100은 4와 같으므로, 0011에 4를 곱하면 답을 얻을 수 있다.
- 2^n으로 곱하는것은 n만큼 왼쪽으로 시프트 하는 것과 같다.
- 즉, 왼쪽으로 두 번 시프트 (0011«2)
1101 ^ (~1101) = 1111
- 어떤비트를 NOT한 값과 그비트를 XOR하면 항상 1이다.
- 즉, a^(~a)는 모든 비트가 1
1101 & (~0 « 2) = 10000
- ~0은 모든 비트가 1이다.
- « 2를 하면 마지막 비트 두 개는 0이되고, 나머지는 1이 된다.
- « n을 하면 마지막 n개의 비트가 0이 된다.
- 이 값과 다른 값을 AND 연산하면 마지막 두 비트의 값을 삭제한 값이된다.

컴퓨터는 일반적으로 정수를 저장할 때 2의 보수 형태로 저장한다. 양수를 표현할 때는 아무 문제 없지만 음수를 표현할 때는 그 수의 절댓값에 부호비트를 1로 세팅한 후 2의 보수를 취한 형태로 표현한다.

n비트 숫자에 대한 2의 보수는 2^n에 대한 보수값과 같다.
이때, n은 부호비트를 뺀 나머지 값을 표현할 때 사용되는 비트의 수이다.
2의 보수 표현 방법
- -K를 N비트의 2진수로 표현하면 concat(1, 2^n-1 -K)이다.
- 또는, 양수로 표현된 이진수를 뒤집고, 1을 더해준 후 부호비트를 맨 앞에 붙여주는 방법이 있다.
예) -3
- 3 //양수로 표현
- 011 //이진수 변환
- 100 // ~
- 101 // + 1
- 1101 // 부호 붙이기

그러면 나머지 비트의 값은 변하지 않은 채 i번째 비트값만 삭제된다.

int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

num의 i번째 비트만 v로 갱신한다.

int updateBit(int num, int i, int v) {
  int mask = ~(1 << i);
  return (num & mask) | (v << i);
}