정수의 세트 비트(Set Bit) 개수를 계산하는 Java 프로그램

정수에서 세트 비트(1로 설정된 비트)의 개수를 세는 것은 비트 조작 분야의 대표적인 기초 문제입니다. 아래는 Java를 사용해 정수의 세트 비트 개수를 계산하는 방법입니다.

예제

import java.io.*;
public class Demo{
   static int set_bits_count(int num){
      int count = 0;
      while (num > 0){
         num &= (num - 1);
         count++;
      }
      return count;
   }
   public static void main(String args[]){
      int num =11;
      System.out.println("The number of set bits in 11 is ");
      System.out.println(set_bits_count(num));
   }
}

출력

The number of set bits in 11 is
3

위 코드는 브라이언 커니핸(Brian Kernighan) 알고리즘을 구현한 것입니다. Demo라는 이름의 클래스 내부에는 'set_bits_count'라는 정적(static) 함수가 정의되어 있습니다. 이 함수는 매개변수로 받은 숫자가 0인지 먼저 확인하고, 0이 아니라면 카운트를 저장할 변수 'count'를 0으로 초기화합니다.

핵심 연산은 num &= (num - 1) 부분입니다. 숫자 자신과 숫자에서 1을 뺀 값을 AND(&) 연산하면 가장 오른쪽에 있는 세트 비트 하나가 제거됩니다. 예를 들어 11은 이진수로 1011인데, 연산을 거칠 때마다 1010 → 1000 → 0000처럼 세트 비트가 하나씩 사라집니다. 이 과정이 한 번 실행될 때마다 'count' 값이 1씩 증가하며, 반복문이 종료되면 최종 count 값이 반환됩니다.

main 함수에서는 세트 비트 개수를 구하고자 하는 값(여기서는 11)을 정의한 뒤, 해당 숫자를 매개변수로 전달하여 함수를 호출합니다. 호출 결과와 관련 메시지가 콘솔에 출력됩니다.

알고리즘의 장점

각 비트를 하나씩 차례대로 검사하는 일반적인 방식은 비트 수만큼 반복해야 하지만, 브라이언 커니핸 알고리즘은 세트 비트의 개수(k)만큼만 반복하므로 1로 설정된 비트가 적은 숫자를 처리할 때 특히 효율적입니다. 시간 복잡도는 O(k), 공간 복잡도는 O(1)입니다.