[코딩인터뷰완전분석] 18일차. 비트조작

🐛 비트조작을 해보자 

• 1. 0110 + 0110 은 0110 * 2 와 같고, 0110 을 왼쪽으로 한번 shift 하는것과 같다.
• 0100 = 4, 0100 * 4 는 왼쪽으로 두번 shift 하는것과 같다. 따라서 0011 을 왼쪽으로 두 번 shift 하면 1100 이 된다.
• 이 연산은 두개를 따로 생각해야 한다. a ^ (~a) 는 항상 1이 된다.
• ~0 은 모두 1이 된다. (1111) 이 값은 and 연산하면 1000 이다.

 

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

1s 는 1111 이고, 0s 는 0000 이다. 편의상 4자리 2진수라 가정한다

한 비트에서 일어나는 일이 다른 비트에 어떤 영향도 주지 않는다.

 

🐛 2의 보수와 음수

컴퓨터는 정수를 저장할 때 2의 보수 형태로 저장한다. 양수는 문제가 없지만 음수는 절대값에 부호비트를 1로 셋팅한 뒤, 2의 보수를 취한 형태로 표현한다.

 

 

🐛 산술 우측 시프트 VS 논리 우측 시프트 

• 산술 우측 시프트(arithmetic right shift)
• 논리 우측 시프트(logical right shift)

 

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

비트값 확인

• 1을 i 만큼 왼쪽으로 shift 하여 0001000 과 같이 만든다 → num과 & 연산을 하여 i 번째 위치 숫자를 제외하고 모두 삭제한다. → 이 값이 1이면 num 의 i 번째 비트는 1이 포함된 숫자이고, 0이면 num 의 i 번째는 0이 포함되었다.

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

 

비트값 채워넣기

• 특정 i 번째 위치에 1을 채워넣는다. 1을 왼쪽으로 shift 하여 001000 과 같이 만들어 or 연산을 한다. 0인 곳은 기존의 값에 영향을 주지 못한다.

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

 

비트값 삭제하기

• 특정 bit 만 삭제한다. getBit 를 반대로 했다. 001000 을 ~ 연산자를 사용해 110111 으로 만들어 and 연산을 하여 특정 위치의 bit 를 제거한다.

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

 

• 최상위 비트에서 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;
}

 

• 0 ~ i 까지의 bit 를 전부 삭제한다. 비트가 모두 1 이면 10진수로 -1 이 된다. -1에 i+1 만큼 시프트 시킨 후 그 값을 & 연산한다.

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

• 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);
}

 

 

 

🏅문제풀이

5.1 삽입

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;
}

 

 

5.3 비트 뒤집기 

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);