Bit Operation(비트연산자)

Integer의 구성(자바)

• Integer = 4 bytes = 32 bits 구성

• 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (32개)

• 2³²-1로 표현 가능

2 진법의 구성

• 0과 1로 구성
• 총 갯수는 2ⁿ 개
• 2진법의 2 bits 구성의 예시는 다음과 같음
  • 0 = 0 0
  • 1 = 0 1
  • 2 = 1 0
  • 3 = 1 1

부호 설정

• 부호를 나타내기 위해 첫 자리를 빼주어야 함
• 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (32개)
• 앞자리가 0 이면 양수, 1이면 음수를 나타냄
• 따라서 표현할 수 있는 숫자 범위는 (-2³¹) ~ (2³¹-1) = -2,147,483,648 ~ 2,147,483,647

2의 보수

• 1 - 1 = 0 을 표현하기 위해서는 2의 보수를 알아야 함
• 어떤 수 + (어떤 수에 대한 2의 보수) = 0 이 되어야 함
  • 4 bits 구성에 첫 자리가 부호를 나타낼 경우 다음과 같은 예시를 들 수 있음
  • 0 = 0 0 0 0
  • 1 = 0 0 0 1
  • 7 = 0 1 1 1
  • -1 = 1 1 1 1
  • -8 = 1 0 0 0
  • 여기서 -1 은 (1 1 1 1) 이어야 함
    • 1 - 1 = (0 0 0 1) + (1 1 1 1) = ( 0 0 0 0 )
    • 따라서 ( 1 1 1 1 ) 은 -1에 대한 2의 보수라고 할 수 있음

비트 연산

• 2 진수 연산의 경우 다음과 같음
  • 덧셈
    • ( 0 1 1 0 ) + ( 0 0 1 0 ) = ( 1 0 0 0 )
    • ( 0 0 1 1 ) + ( 0 0 1 0 ) = ( 0 1 0 1 )
  • 뺄셈
    • ( 0 1 1 0 ) - ( 0 0 1 1 ) = ( 0 0 1 1 )
  • 곱셈
    • ( 0 0 1 1 ) * ( 0 1 0 1 ) = ( 0 1 0 1 ) + ( 0 1 0 1 0 ) = ( 1 1 1 1 )
• 연산자
  • OR 연산 (두 개중에 하나라도 1이면 1)
    • 0 | 0 = 0
    • 1 | 0 = 1
    • 1 | 1 = 1
    • ( 0 0 1 1 ) | ( 0 1 0 1 ) = ( 0 1 1 1 )
    • ( x x x x ) | ( 0 0 0 0 ) = ( x x x x ) (x는 0 또는 1)
    • ( x x x x ) | ( 1 1 1 1 ) = ( 1 1 1 1 ) (x는 0 또는 1)
    • ( x x x x ) | ( x x x x ) = ( x x x x ) (x는 0 또는 1)
  • AND 연산 (두 개 모두 1이면 1)
    • 0 & 0 = 0
    • 1 & 0 = 0
    • 1 & 1 = 1
    • ( 0 0 1 1 ) & ( 0 1 0 1 ) = ( 0 0 0 1 )
    • ( x x x x ) & ( 0 0 0 0 ) = ( 0 0 0 0 ) (x는 0 또는 1)
    • ( x x x x ) & ( 1 1 1 1 ) = ( x x x x ) (x는 0 또는 1)
    • ( x x x x ) & ( x x x x ) = ( x x x x ) (x는 0 또는 1)
  • NOT 연산 ( 0 과 1이 반대되는 경우 )
    • ~ 0 = 1
    • ~ 1 = 0
    • ~ ( 0 1 0 1 ) = ( 1 0 1 0 )
  • XOR 연산 ( 두 개가 서로 다른 값을 가질 경우 1)
    • 0 ^ 0 = 0
    • 1 ^ 0 = 1
    • 1 ^ 1 = 0
    • ( 1 1 0 1 ) ^ ( 0 1 0 1 ) = ( 1 0 0 0 )
    • ( x x x x ) ^ ( 0 0 0 0 ) = ( x x x x ) (x는 0 또는 1)
    • ( x x x x ) ^ ( 1 1 1 1 ) = ~ ( x x x x ) (x는 0 또는 1)
    • ( x x x x ) ^ ( x x x x ) = ( 0 0 0 0 ) (x는 0 또는 1)
  • Shift 연산
    • Left Shift
      • ( 1 0 0 1 ) << 2 = ( 1 0 0 1 0 0 )
    • Right Shift
      • ( 1 0 0 1 ) >> 2 = ( 1 0 )
  • Signed Shift 연산
    • logical rigth shift (부호무관)
      • ( 1 0 1 1 0 1 0 1 ) >>> ( 0 1 0 1 1 0 1 0 ) = -75 >>> 90
    • arithmetic right shift (부호유지)
      • ( 1 0 1 1 0 1 0 1 ) >> ( 1 1 0 1 1 0 1 0 ) = -75 >> -38

Get Bit

• int num = 9, int i = 3
• 숫자 9의 세번째 인덱스를 가지고 올 경우
  • 9 = ( 0 0 0 . . . 1 0 0 1 )
  • 1 <<< 3 = ( 1 0 0 0 )
  • 이 두개를 AND 연산으로 계산하면 해당 자리의 비트를 가져올 수 있음
  • 즉, 1 <<< i 를 이용해서 해당 숫자의 인덱스에 위치한 비트를 가져올 수 있음

Set Bit

• int num = 9, int i = 3
• 숫자 9의 세번째 인덱스를 셋팅할 경우
  • 9 = ( 0 0 0 . . . 1 0 0 1 )
  • 1 <<< 3 = ( 1 0 0 0 )
  • 이 두개를 OR 연산으로 계산하면 해당 자리의 비트를 셋팅할 수 있음
  • 즉, 1 <<< i 를 이용해서 해당 숫자의 인덱스에 위치한 비트를 셋팅할 수 있음

Clear Bit (0으로 바꾸기)

• int num = 9, int i = 3
• 숫자 9의 세번째 인덱스를 0으로 바꿀 경우
  • 9 = ( 0 0 0 . . . 1 0 0 1 )
  • 1 << 3 = ( 1 0 0 0 ) 에서 ~ ( 1 0 0 0 ) = ( 0 1 1 1 )
  • 이 두개를 AND 연산으로 계산하면 해당 자리의 비트를 0으로 바꿀 수 있음
  • 즉, 1 << i 를 이용해서 해당 숫자의 인덱스에 위치한 비트를 0으로 셋팅할 수 있음

Clear Left Bits (기준 인덱스 왼쪽을 전부 0으로 바꾸기)

• int num = 169, int i = 3
  • 1 << 3 = ( 1 0 0 0 ) 에서 ( 1 0 0 0 ) - 1 = ( 0 1 1 1 )
    • ~ 을 사용하면 왼쪽의 숫자들도 같이 바꾸지만 1을 빼면 오른쪽만 바뀜
  • 이 두개를 AND 연산으로 계산하면 기준점의 왼쪽 비트를 0으로 바꿀 수 있음

Clear Right Bits (기준 인덱스 포함 오른쪽을 전부 0으로 바꾸기)

• int num = 169, int i = 3
  • -1 << (3+1) = ( 1 1 1 1 ... 0 0 0 0 )
  • 이 두개를 AND 연산으로 계산하면 기준점 포함 오른쪽 비트를 0으로 바꿀 수 있음

Update Bits

• int num = 169, int i = 3, boolean val = true
  • ( x x x x x x x ) & ( 1 1 1 0 1 1 1 ) = ( x x x 0 x x x )
  • ( x x x 0 x x x ) | ( 0 0 0 v 0 0 0) = ( x x x v x x x)