[swift] 프로그래머스 -2개 이하로 다른 비트

프로그래머스

---

실패 풀이

func solution(_ numbers:[Int64]) -> [Int64] {
    return numbers.map {
        var n = $0 + 1
        for i in n... {
            if (i^$0).nonzeroBitCount <= 2 {
                n = i
                break
            }
        }
        return n
    }
}
// 비트연산자 ^ 는 서로의 비트가 다를 때 1을 반환한다.
// nonzeroBitCount는 비트가 1일 때의 개수를 센다.

풀이 키워드

비트연산자
입력값에 +1을 더해가며
입력값과 더한 값의 비트가 2이상 차이나지 않는다면 반환

해당 풀이는 시간초과로 실패

 

성공 풀이

func solution(_ numbers:[Int64]) -> [Int64] {
    return numbers.map {
        let next = ~$0 & ($0+1)
        return ($0 | next) & ~(next >> 1)
    }
}

풀이 키워드

비트연산자
비트가 2개 이하로 다른 수 중 제일 작은 수를 구하는 방법은
비트의 제일 오른쪽 0이 1로 바뀌고
0에서 1로 바뀐 자리의 오른쪽의 숫자를 0으로 바꾸는 겁니다.
ex) 0101 -> 0110

만약 마지막 자리에 0이 있었다면, 마지막 자리만 1로 바꾸면 됩니다.
마지막 자리가 0일 때는 짝수를 의미하므로
짝수일 때는 10진수에서 +1만 해도
비트가 2개 이하로 다른 수 중 제일 작은 수를 구할 수 있습니다.
ex) 1110 -> 1111

모든 수가 1로 채워져 있는 비트라면
첫자리에 1이 붙으면서, 원래 첫자리였던 1은 0이 되겠죠!
ex) 1111 -> 10111

예시)
입력: 4 (2진수: 0100)

next = ~0100 & (0100 +1)
next = 1011 & 0101
next = 0001

return (0100 | 0001) & 1111
return 0101 & 1111
return 0101

출력: 5(2진수: 0101)

---

입력: 7 (2진수: 111)

next = ~0111 & (0111+1)
next = 1000 & 1000
next = 1000

return (0111 | 1000) & ~(1000 >> 1)
return 1111 & ~(0100)
return 1111 & 1011
return 1011

출력: 11(2진수: 1011)

---