C++로 숫자의 이진수 표현에서 가장 긴 연속된 1의 길이 구하기

어떤 수 n이 주어졌을 때, 이 숫자를 2진수(이진수)로 표현했을 때 나타나는 1 중에서 가장 길게 연속된 구간의 길이를 구하는 문제입니다.

문제 예시

예를 들어 입력값이 n = 312라고 가정해 보겠습니다. 312를 2진수로 변환하면 100111000이 되는데, 여기서 1이 연속으로 등장하는 가장 긴 구간은 3개이므로 출력 결과는 3이 됩니다.

해결 접근 방법

이 문제는 숫자의 각 비트를 하나씩 확인하면서 연속된 1의 개수를 세는 방식으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.

결과값 ret과 현재 연속 길이 len을 각각 0으로 초기화합니다.
i를 0부터 31까지 반복하면서 다음을 수행합니다.
(n >> i) & 1 결과가 참, 즉 i번째 비트가 1이라면 len을 1 증가시킵니다.
그렇지 않고 비트가 0이라면 연속 구간이 끊긴 것이므로 len을 0으로 초기화합니다.
매 반복마다 ret과 len 중 더 큰 값을 ret에 저장하여 최댓값을 갱신합니다.

모든 비트를 확인한 후 ret을 반환하면, 그 값이 곧 가장 긴 연속된 1의 길이가 됩니다.

C++ 구현 코드

아래는 위 알고리즘을 실제로 구현한 C++ 소스 코드입니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(int n) {
      int ret = 0;
      int len = 0;
      for(int i = 0; i < 32; i++){
         if((n >> i) & 1){
            len++;
         }else{
            len = 0;
         }
         ret = max(ret, len);
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << ob.solve(312);
}

입력

출력

코드 설명

(n >> i) & 1은 n을 오른쪽으로 i비트 시프트한 뒤 마지막 비트와 1을 AND 연산하여, i번째 비트가 1인지 0인지 판별하는 비트 연산 기법입니다. 정수형(int)은 일반적으로 32비트이므로 32번 반복하면 모든 비트를 검사할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(32), 즉 O(1)로 매우 효율적입니다.