복제
250px-Divmod.svg.png

비트 연산, 비트 조작 bit를 다뤄보자

태그
Bit
Binary
공개여부
작성일자
2021/01/09
코드를 최적화 할 때 유용하게 사용되는 기법중에 하나이다. 비트 연산은 손으로 풀 수 있을만큼 익숙할 필요가 있다. 알고리즘에서 Big O를 모두 최적화 했을때, 배열을 다뤄야 할 때 비트연산을 고민하면 더 좋은 성능을 기대할 수 있다.
이 컨텐츠는 코딩 인터뷰 완전분석 에서 정말 재미있게 읽었던 비트연산 부분을 발췌했다.
손으로 비트 조작 해보기
1.
아래 설명하는 트릭으로 풀기
2.
10진수로 변경하고 계산한 후 2진수로 변경한다.
Screen_Shot_2020-11-26_at_23.11.30.png
정답
위 표에서 가장 오른쪽 열 4개만 살펴본다.
1.
0110 + 0110 은 0110 * 2 와 같고, 0110 을 왼쪽으로 한번 shift 하는것과 같다.
2.
0100 = 4, 0100 * 4 는 왼쪽으로 두번 shift 하는것과 같다.
0011 을 왼쪽으로 두 번 shift 하면 1100 이 된다.
3.
이 연산은 두개를 따로 생각해야 한다. a ^ (~a) 는 항상 1이 된다.
4.
~0 은 모두 1이 된다. (1111) 이 값은 and 연산하면 1000 이다.
비트 조작을 할 때 알아야 할 사실들과 트릭들
암기하기 보단 이해가 필요하다.
1s 는 1111 이고, 0s 는 0000 이다. 편의상 4자리 2진수라 가정한다
Screen_Shot_2020-11-26_at_23.58.04.png
풀이
한 비트에서 일어나는 일이 다른 비트에 전혀 영향을 주지 않는다.
2의 보수와 음수
보수의 개념
컴퓨터는 정수를 저장할 때 2의 보수 형태로 저장한다. 양수는 문제가 없지만 음수는 절대값에 부호비트를 1로 셋팅한 뒤, 2의 보수를 취한 형태로 표현한다.
N비트 음수에 대한 2의 보수는 2n2^n 에 대한 보수와 같다.
4비트로 표현된 정수 -3 으로 증명해보자
4비트 중 하나는 부호를 표현한 값이다. → 3비트
-3: 절대값 3의 232^3 = 8의 보수와 // -3의 2의 보수는 같다
3은 8의 보수가 5이다. → 0101
-3 은 1101 이다. (제일 앞에 캐리가 1이면 음수를 뜻한다)
-K를 N비트 2진수로 표현하면 concat(1, 2N1K2^{N-1}-K) 가 된다.
2의 보수는 1 → 0, 0 → 1로 전환하고(^1s) +1을 한다. 그리고 부호가 있으면 앞에 1을 붙인다.
Screen_Shot_2020-11-27_at_21.49.32.png
4비트 정수값을 위와 같이 표현한다.
왼쪽과 오른쪽의 절대값을 합치면 항상 8이 된다. 왜 그럴까?
산술 우측 시프트 vs 논리 우측 시프트
우측 시프트 연산은 두가지가 존재한다.
산술 우측 시프트(arithmetic right shift)
2로 나눈것과 같다.
Screen_Shot_2020-11-27_at_22.19.19.png
가장 앞에 1을 계속 채워넣는다
모두 1로 채워지면(1s) -1 이 된다.
부호를 바꾸지 않는다
>> 연산과 같다.
논리 우측 시프트(logical right shift)
비트를 우측으로 옮긴 다음에 최상위 비트에 0을 넣는다
Screen_Shot_2020-11-27_at_22.01.11.png
회색 부분이 부호 비트를 나타낸다
비트를 옮길 때 보이는 것 처럼 움직인다.
>>> 연산과 같다.
부호가 바뀐다.
논리 shift 를 계속 사용하면 0이 된다.
기본적인 비트 조작: 비트값 확인 및 채워넣기
비트값 확인
1을 i 만큼 왼쪽으로 shift 하여 0001000 과 같이 만든다 → num과 & 연산을 하여 i 번째 위치 숫자를 제외하고 모두 삭제한다. → 이 값이 1이면 numi 번째 비트는 1이 포함된 숫자이고, 0이면 numi 번째는 0이 포함되었다.
boolean getBit(int num, int i) { return ((num & (1 << i)) != 0); }
Java
비트값 채워넣기
특정 i 번째 위치에 1을 채워넣는다
1을 왼쪽으로 shift 하여 001000 과 같이 만들어 or 연산을 한다. 0인 곳은 기존의 값에 영향을 주지 못하고, i 번째 값은
int setBit(int num, int i) { return num | (1 << i); }
Java
비트값 삭제하기
특정 bit 만 삭제한다.
getBit 를 반대로 했다. 001000~ 연산자를 사용해 110111 으로 만들어 and 연산을 하여 특정 위치의 bit 를 제거한다
int clearBit(int num, int i) { int mask = ~(1 << i); return num & mask; }
Java
최상위 비트에서 i번째 비트까지 모두 삭제하기
i 번째 bit 를 셋팅하고 -1 을 하면 최상위 부터 i 번째 까지 0으로 채워지고, 그 뒤는 1로 채워진다
이 값을 num& 연산을 하면 앞을 0 때문에 0으로 지워지고 그 뒤는 모두 1 때문에 그대로 남아 있는다.
int clearBitsFromHead(int num, int i) { int mask = (1 << i) - 1; return num & mask; }
Java
0 ~ i 까지의 bit 를 전부 삭제한다.
비트가 모두 1 이면 10진수로 -1 이 된다. -1에 i+1 만큼 시프트 시킨 후 그 값을 & 연산한다.
int clearBitFromTail(int num, int i) { int mask = (-1 << (i+1)); return num * mask; }
Java
i번째 bit 를 v로 변경하기
int updateBit(int num, int i, boolean bitIs1) { int value = bitIs1 ? 1 : 0; int mask = ~(1 << 1); return (num & mask) | (value << i); }
Java
면접 문제
5.1 삽입
두개의 32비트 수 N, M 이 주어지고, 비트 위치 i, j가 주어졌을 때, M을 N에 삽입하는 method를 구현하라.
M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝난다.
j번째 비트에서 i번째 비트까지에는 M을 담기 충분한 공간이 있다고 가정한다.
입력 N = 1000000000, M = 10011, i = 2, J =6
출력 N = 10001001100
public int bitInsert(int m, int n, int i, int j) { m = bitDeleteFrom(m, j, i); n = leftBitShift(n, i); System.out.println("m: " + Integer.toBinaryString(m) + ", n: " + Integer.toBinaryString(n) + ", m + n: " + Integer.toBinaryString(m+n)); return m + n; } private int bitDeleteFrom(int num, int start, int end) { int mask = (1 << (start + 1)) - 1; mask = mask >> end; mask = mask << end; return num & ~mask; } private int leftBitShift(int num, int j) { return num << j; }
Java
5.3 비트 뒤집기
어떤 정수가 주어졌을 때 이 정수의 비트 하나를 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 코드를 작성하라.
private String convert1bit(int data) { String[] d = String.valueOf(data).split("0"); int max = 0; int maxIndex = 0; for (int i = 0; i < d.length; i++) { if (d[i].length() > max) { max = d[i].length(); maxIndex = i; } } String result = ""; if (maxIndex < d.length-1 && d[maxIndex+1] != "") { result = d[maxIndex] + "1" + d[maxIndex+1]; } if (maxIndex > 0 && d[maxIndex-1] != "") { String re = d[maxIndex-1] + "1" + d[maxIndex]; if (result.length() < re.length()) { return re; } } return result; } Integer.toBinaryString(1024);
Java
2진수를 문자로 바꾸어 split("0") 하고, 앞 뒤 문자열을 비교한다
5.5 디버거
다음 코드가 하는 일을 설명하라.
((n & (n-1)) == 0)
SQL
n 은 2의 거듭제곱인가?
1000 & 0111 (= 1000 - 0001) ---------------------- 0000 -> true
Java
1100 & 1011 (= 1100 - 0001) ----------------------- 1000 -> false
Java
Made with 💕 and Oopy