[LeetCode] 190. Reverse Bits - Kotlin

 

class Solution {
    fun reverseBits(n: Int): Int {
        var res = 0
        var num = n
        for (i in 0 until 32) {
            res = res shl 1        // 1. res를 왼쪽으로 1비트 이동
            res += num and 1       // 2. num의 최하위 비트를 res에 추가
            num = num shr 1        // 3. num을 오른쪽으로 1비트 이동
        }
        return res
    }
}

 

주요 비트 연산

1. shl (Shift Left):
   
   • 비트를 왼쪽으로 이동. 오른쪽은 0으로 채워짐.
   • 예: 0010 shl 1 → 0100.
2. shr (Shift Right):
   
   • 비트를 오른쪽으로 이동. 왼쪽은 부호 비트로 채워짐(음수면 1, 양수면 0).
   • 예: 0100 shr 1 → 0010.
3. and (Bitwise AND):
   
   • 두 비트가 모두 1일 때만 1 반환.
   • num and 1은 최하위 비트(LSB)를 추출 (0 또는 1).
     
     
     

과정 상세 설명

 

입력 예시로 n = 13 (이진수: 00001101, 32비트로 확장)을 사용해 단계별로 살펴보겠습니다. 목표는 00001101을 뒤집어 10110000 (10진수 176)을 만드는 것입니다.

 

초기 상태

• res = 0 (00000000).
• num = 13 (00001101).

1단계: 루프 0~31

• i = 0:
  
  1. res = res shl 1:
     
     • 00000000 → 00000000 (아직 이동할 비트 없음).
  2. res += num and 1:
     
     • num = 00001101, num and 1 = 1 (최하위 비트 1).
     • res = 00000000 + 1 = 00000001.
  3. num = num shr 1:
     
     • 00001101 → 00000110.
• 상태: res = 00000001, num = 00000110.
• i = 1:
  
  1. res = res shl 1:
     
     • 00000001 → 00000010.
  2. res += num and 1:
     
     • num = 00000110, num and 1 = 0.
     • res = 00000010 + 0 = 00000010.
  3. num = num shr 1:
     
     • 00000110 → 00000011.
• 상태: res = 00000010, num = 00000011.
• i = 2:
  
  1. res = res shl 1:
     
     • 00000010 → 00000100.
  2. res += num and 1:
     
     • num = 00000011, num and 1 = 1.
     • res = 00000100 + 1 = 00000101.
  3. num = num shr 1:
     
     • 00000011 → 00000001.
• 상태: res = 00000101, num = 00000001.
• i = 3:
  
  1. res = res shl 1:
     
     • 00000101 → 00001010.
  2. res += num and 1:
     
     • num = 00000001, num and 1 = 1.
     • res = 00001010 + 1 = 00001011.
  3. num = num shr 1:
     
     • 00000001 → 00000000.
• 상태: res = 00001011, num = 00000000.
• i = 4~31:
  
  • num이 이미 0이므로 num and 1 = 0.
  • res는 계속 왼쪽으로 이동하며 0 추가.
  • 최종: res = 10110000 (32비트로 확장: 00000000...10110000).

결과

• 입력: 00001101 (13).
• 출력: 10110000 (176).