Ch5. 비트 조작

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 산술 우측 시프트와 논리 우측 시프트

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

    • 산술 우측 시프트는 기본적으로 2를 나눈 결과와 같다.

    • 이는 비트를 오른쪽으로 옮기긴 하지만 부호비트는 바꾸지 않는다.

    • 

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

    • 논리 우측 시프트는 비트를 옆으로 옮긴 뒤 최상위 비트(most significant bit)에 0을 넣는다.

    • 

• 비트 조작하기

  • 비트값 확인

    • i 번째 비트의 값이 0인지 1인지 확인하고자 한다.

    • 이를 위해 1을 i만큼 시프트해서 00010000 과 같은 값을 만든다.

    • 이를 AND 연산을 통해 i 번째 비트를 제외한 나머지 비트를 모두 삭제한 뒤, 이 값을 0 과 비교한다.

    • 만약 이 값이 0이 아니라면 i 번째 비트는 1일 것이며, 0이라면 i 번쨰 비트는 0이어야 한다.

      1 2	def getBit(num, i): return ((num & (1<<i)) != 0)

    • 위의 함수를 통해 i 번째 비트의 값을 확인할 수 있다.

  • 비트값 채워넣기

    • i 번째 비트를 1로 바꾸려고 한다.

    • 이를 위해 1을 i만큼 시프트해서 00010000 과 같은 값을 만든다.

    • 이를 OR 연산을 통해 num의 i번째 값만을 바꿔줄 수 있다.

      1 2	def setBit(num, i): return num | (1 << i)

    • 위의 함수를 통해 i 번쨰 비트를 1로 바꿔줄 수 있다.

  • 비트값 삭제하기

    • i 번쨰 비트값만 삭제하고자 한다.

    • 이를 위해 11101111 과 같은 마스크를 만들어야 한다.

    • 1 을 num 의 길이보다 1 크게 쉬프트한 뒤 1을 빼서 11111111 과 같은 값을 만든다.

    • 그리고 1을 i 만큼 쉬프트해서 00010000 과 같은 값을 만든다.

    • 만든 두 개의 값을 XOR 연산을 통해 11101111 과 같은 마스크를 만든다.

    • 마스크와 num 을 AND 연산하면 i 번쨰 비트만 삭제된다.

      1 2 3 4 5 6

      def clearBit(num, i): length = len(bin(num))-2 temp1 = (1<<(length+1)) -1 ## 11111111 만들기 temp2 = 1<<i ## 00010000 만들기 mask = temp1 ^ temp2 ## 두개를 합쳐서 마스크 만들기 return num & mask

    • 위의 함수를 통해 i 번쨰 비트만 삭제할 수 있다.

Ch5. 연습문제 코드

CtCI_Ch5_Python