책너두 (코딩 인터뷰 완전분석) 18일차 (170p, 5.1~5.3)

메모

05. 비트조작

• 코드를 최적화할 때 융요하게 사용되는 기법으로 활용됨.
• 코드를 작성하는 것 뿐만 아니라 손으로도 그릴수 있도록 익숙해지는 것이 좋음.

손으로 비트 조작 해보기

• 세번째 열 트릭은 다음과 같음.
  • 0110 + 0110 = 0110 * 2 와 같음. 따라서 0110 을 왼쪽으로 한 번 시프트 한 것과 같음.
  • 0100은 4와 갓고, 4를 곱하는 것은 왼쪽으로 두 번 시프트하는 것과 같음.
  • 따라서 0011을 왼쪽으로 두 번 시프트하면 1100이 됨.
  • 어떤 비트와 그 비트를 부정한 값을 XOR 하면 항상 1이 됨. 따라서 a^(~a) 를 하면 모든 비트가 1이 됨.
  • ~0을 하면 모든 비트가 1이 됨. 따라서 ~0 << 2를 하면 마지막 비트 두 개는 0이되고 나머지는 모두 1이 됨. 이값과 다른 값을 AND 연산하면 마지막 두 비트의 값을 삭제한 값을 얻는다.

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

• 비트 조작할 때, 다음 표현식을 알아 두면 좋음.
  • 암기는 하지 말라
  • 각 표현식들이 왜 참이 되는지 깊이 생각해 보길 바람.
  • 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의 보수 형태로 저장함.
  • 양수 표현시에는 아무 문제가 없지만, 음수를 표현할 때, 그 수의 절대값에 부호비트를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현함.

면접 문제

5.1 삽입

• 두 개의 32비트 수 N과 M이 주어지고, 비트 위치 i와 j가 주어졌을 때, M을 N에 삽입하는 메서드를 구현하라. M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝난다. j번째 비트에서 i번쨰 비트까지에는 M을 담기 충분한 공간이 있다고 가정한다. 다시 말해, M = 10011이라면, j와 i 사이에 적어도 다섯 비트가 있다고 가정해도 된다는 것이다. j = 3이고 i = 2인 경우처럼 M을 삽입할 수 없는 상황은 생기지 않는다고 봐도 된다.

5.2 2진수를 문자열로

• 0.72와 같이 0과 1 사이의 실수가 double 타입으로 주어졌을 때, 그 값을 2진수 형태로 출력하는 코드를 작성하라. 길이가 32이하인 문자열로 2진수로 정확하게 표현할 수 없다면 ERROR을 출력하라.

5.3 비트 뒤집기

• 어떤 정수가 주어졌을 때 여러분은 이 정수의 비트 하나를 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 코드를 작성하라.