모든 챌린지
보통 0명 해결 정답률 0%

비트 뒤집기

수의 하위 width개 비트의 순서를 뒤집습니다.

배우게 될 내용

  • AND 1로 가장 낮은 비트를 읽을 수 있다
  • 시프트로 수를 한 비트씩 만들어 갈 수 있다
  • 고정된 비트 폭을 지킬 수 있다

문제

원문 보기 (영어)

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

예시

예시 1
입력:
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입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.