문제
n을 정확히 width개의 비트로 된 2진수로 쓰고(필요하면 앞에 0을 채웁니다) 그 비트를 거꾸로 읽으세요. n = 6, width = 4이면 6은 0110이고 뒤집어도 0110이므로 결과는 6입니다. width = 8이면 00000110을 뒤집은 01100000이 되어 96입니다. 비트 뒤집기는 고속 푸리에 변환(FFT)이나 일부 해싱 기법에 쓰입니다.
reverse_the_bits(n, width) 함수를 구현하세요.
입력
n: width개의 비트 안에 들어가는 음이 아닌 정수입니다.
width: 뒤집을 비트의 개수입니다.
출력
뒤집은 width비트 패턴의 값을 반환합니다.
제약 조건
1 ≤ width ≤ 63
0 ≤ n < 2^width
예시
입력:
n = 6
width = 8
예상 출력:
expected = 96
입력:
long long n = 6;
long long width = 8;
예상 출력:
long long expected = 96;
입력:
long n = 6;
long width = 8;
예상 출력:
long expected = 96;
설명
6은 8비트로 00000110이고, 뒤집으면 01100000이 되어 96입니다.
입력:
n = 1
width = 3
예상 출력:
expected = 4
입력:
long long n = 1;
long long width = 3;
예상 출력:
long long expected = 4;
입력:
long n = 1;
long width = 3;
예상 출력:
long expected = 4;
설명
1은 001이고, 뒤집으면 100이 되어 4입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
width번 반복합니다. n의 가장 낮은 비트를 꺼낸 다음 n을 오른쪽으로 시프트하세요.
힌트 2
방금 꺼낸 비트를 더하기 전에 결과를 왼쪽으로 한 칸 시프트하세요.
힌트 3
n의 앞자리 0은 결과의 뒷자리 0이 되는데, 반복 횟수가 고정되어 있으므로 자연히 처리됩니다.
예상 복잡도
시간 O(width), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.