2개 이하로 다른 비트

문제

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10^15

---

입출력 예

numbers	result
[2,7]	[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

 

접근 및 풀이

비트 연산자를 이용해 풀었는데 실패했다. 비트연산자는 연산 전에 피연산자를 32비트의 정수로 변환하고 32비트를 초과하는 수는 무시하기 때문에 제대로된 연산을 할 수 없었다. 제한 사항에서 제시된 숫자의 최대 크기가 비트연산자가 지원하는 32비트를 초과하기 때문에 실패했다. 작은 수 부터 규칙을 찾아내 문제를 풀었다

코드

function solution(numbers) {
  let result = numbers.map(e=>{
    let binary = e.toString(2).split("");
    let rightOne = 0;
    if (e%2 === 0) return e+1;
    for (let i = binary.length - 1; i >= 0; i--) {
      if (binary[i] === "0") break;
      if (rightOne === 0) rightOne = 1;
      else rightOne = rightOne * 2 + 1;
    }

    return e - rightOne + (rightOne + 1 + ((rightOne - 1) / 2));
  })
  return result
}

출처

https://programmers.co.kr/learn/courses/30/lessons/77885