[코딩 인터뷰]개념과 알고리즘 - 비트 조작

 

[ 손으로 비트 조작해보기 ]

 비트 조작에 익숙하지 않다면 손으로 다음의 연습문제들을 풀어보는 것이 좋습니다. 비트는 1과 0만을 가지는 2진수로 +, -와 *의 경우 똑같이 연산하시면 됩니다.

연산자	기능
+	더하기 연산
-	뺴기 연산
*	곱셈 연산
&	비교하는 두 비트가 1이면 1, 그 외의 모든 경우는 0인 연산 (AND)
|	비교하는 두 비트가 0이면 0, 그 외의 모든 경우는 1인 연산 (OR)
^	비교하는 비트 같으면 0 다르면 1인 연산 (XOR)
~	모든 비트 반전하는 연산(NOT)
>>	비트 열을 오른쪽으로 이동 연산
<<	비트 열을 왼쪽으로 이동 연산

⭐ 문제를 단순화하기 위해서 모든 숫자는 4비트 숫자라고 가정합니다.

 

👀 연습 문제

0110 + 0010	0011 * 0101	0110 + 0110
0011 + 0010	0011 * 0011	0100 * 0011
0110 - 0011	1101 >> 2	1101 ^ (~1101)
1000 - 0010	1011 ^ 0101	1101 & (~0 << 2)

풀이 및 정답▼

 

---

 

 

[ 비트 조작을 할 때 알아야 할 사실들과 트릭들 ]

 비트 조작 문제를 풀 때 다음의 표현식들을 알아 두면 좋습니다.

⭐ '0s'는 모든 비트가 0인 값이고, '1s'는 모든 비트가 1인 값입니다.

x ^ 0s = x	x & 0s = 0	x | 0s = x
x ^ 1s = ~x	x & 1s = x	x | 1s = 1s
x ^ x = 0	x & x = x	x | x = x

 

 

[ 2의 보수와 음수 ]

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

⭐ N비트 숫자에 대한 2의 보수는 2의 N승에 대한 보수값과 같습니다.

⭐ N : 부호비트를 뺀 나머지 값을 표현할 때 사용되는 비투의 수

👀 다른 방법

: 양수로 표현된 2진수를 뒤집은 뒤 1을 더해주는 것입니다.

 

 

[ 산술 우측 시프트 vs 논리 우측 시프트 ]

👀 산술 우측 시프트(arrithmetic right shift)

: 비트를 오른쪽으로 옮기긴 하지만 부호 비트는 바꾸지 않습니다. 따라서 이 연산은 2로 나눈 효과가 있고 >>연산과 같습니다.

산술 우측 시프트

⭐ Java Code

int repeatedArithmeticShift(int x, int count){
    for(int i=0; i<count; i++){
        x >>= 1;
    }
    return x;
}

 

👀 논리 우측 시프트(logifal right shift)

: 비트를 옆으로 옮긴 다음에 최상위 비트에 0을 넣습니다. 일반적으로 비트를 옮길 때 보이는 것처럼 움직이며, >>> 연산과 같습니다.

논리 우측 시프트

⭐ Java Code

int repeatedLogicalShift(int x, int count){
    for(int i=0; i<count; i++){
        x >>>= 1;
    }
    return x;
}

 

 

[ 기본적인 비트 조작: 비트값 확인 및 채워 넣기 ]

 다음의 연산들은 굉장히 중요하므로 반드시 알고 있어야 합니다.

 

👀 비트 값 확인

 알고 싶은 i번째 비트만큼 1을 시프트 한 뒤 and 연산으로 나머지 비트 삭제한 뒤 값을(1 or 0) 확인합니다.

boolean getBit(int num, int i){
    return ((num & (1 << i)) != 0);
}

 

👀 비트 값 채워 넣기

 1을 i번째 비트만큼 시프트 해서 or 연산으로 num의 i번째 비트 값을 바꾼 값을 반환합니다.

int setBit(int num, int i){
    return num | (1 << i);
}

 

👀 비트값 삭제하기

 비트 값 채워넣기와 반대로 진행합니다. 1을 i번만큼 시프트 한 값에 not 연산을 이용해 i번째 값만 0으로 만든 뒤 num과 and 연산한 값을 반환합니다.

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

❗ 최상위 비트에서 i번째 비트까지 모두 삭제하려면?

  → i번째 비트 밑은 모두 1로 만들고 그 위로는 모두 0으로 만든 뒤 num과 and 연산

int clearBitsMSBthroughI(int num, int i){
    int mask = (1 << i) -1;
    return num & mask;
}

❗ i번째 비트에서 0번째 비트까지 모두 삭제하려면?

  → i번째 비트 위로는 모두 1로 만들고 하위 i개 비트는 모두 0으로 만든 뒤 num과 and 연산

int clearBitsIthrough0(int num, int i){
    int mask = (-1 << (i + 1));
    return num & mask;
}

 

👀 비트값 바꾸기

 i번째 비트 값을 v로 바꾸고 싶다면 특정한 값(i번째를 제외한 모든 값은 1이고 i번째는 0인 값)과 and 연산을 이용하여 i번째 비트값을 삭제하고 v를 i번째로 시프트 한 뒤 or 연산한 값을 반환합니다.

int updateBit(int num, int i, boolean bitIs1){
    int value - bitIs1 ? 1 : 0;
    int mask = ~(1 << i);
    return (num & mask) | (value << i);
}