C# 프로그램: 주어진 정수의 이진 표현에서 가장 긴 연속된 1의 길이 찾기

개요

정수의 이진 표현에서 가장 긴 연속된 1의 길이를 구하려면 비트 왼쪽 시프트 연산자(<<)를 활용할 수 있습니다. 핵심 아이디어는 숫자를 자기 자신을 왼쪽으로 한 비트 시프트한 값과 비트 AND 연산을 수행하는 것입니다.

i = (i & (i << 1));

이 연산은 인접한 두 비트가 모두 1일 때만 결과가 1이 되므로, 반복할 때마다 연속된 1의 시퀀스가 한 칸씩 줄어들게 됩니다.

알고리즘 동작 방식

위 연산을 값이 0이 될 때까지 반복하고, 반복 횟수를 변수 count로 세면 그 값이 곧 가장 긴 연속된 1의 길이가 됩니다.

while (i != 0) {
   i = (i & (i << 1));
   count++;
}

예제

여기서는 150을 예로 들어 보겠습니다.

150의 이진 표현은 10010110입니다. 따라서 가장 긴 연속된 1의 길이는 2입니다.

C# 전체 코드

using System;
class Demo {
   private static int findConsecutive(int i) {
      int count = 0;
      while (i != 0) {
         i = (i & (i << 1));
         count++;
      }
      return count;
   }

   // 드라이버 코드
   public static void Main() {
      // 150의 이진 표현은 10010110
      Console.WriteLine(findConsecutive(150));
   }
}

출력 결과

2

단계별 동작 원리

150(10010110)에 대해 이 알고리즘이 어떻게 동작하는지 살펴보겠습니다.

• 1단계: 10010110 & (10010110 << 1) → 00000100, count = 1
• 2단계: 00000100 & (00000100 << 1) → 00000000, count = 2
• 3단계: 값이 0이 되었으므로 루프 종료 후 count 반환

최종적으로 반환되는 값 2는 150의 이진 표현에서 가장 긴 연속된 1의 길이와 정확히 일치합니다. 이 알고리즘은 시간 복잡도 O(log n)으로 매우 효율적이며, 비트 연산만 사용하기 때문에 추가 메모리 없이 문제를 해결할 수 있습니다.