[Java] int 정수 변수 비트의 1의 개수 세기 / 예제, 원리

본 게시글은 데스크탑 환경에서 읽으시기를 권장합니다. 

---

int 정수,  \( 2^{32} \) 이하의 정수를 2진수로 변환하였을 때 가지고 있는 1의 개수를 세어줍니다. 

 

int정수를 파라미터로 받고 마스크를 오른쪽으로 옮기며 and 연산을 통해 비트에 들어있는 1의 개수를 셉니다. 

리턴 값으로 1의 개수를 가집니다.  

public static int bitCount(int input) {
      int count = 0;
      int mask = 1 << 31;

      while (true){
          if (mask == 0){
              break;
          }
          if((mask & input) == 0){
              
          }else {
              count++;
          }

          mask = mask >>> 1;
      }

      return count;
  }

---

728x90

---

다음은 위의 함수를 테스트 하는 코드입니다. 

import java.util.Scanner;

public class BitCount {
  public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      System.out.print("32-bit 숫자 입력: ");
      
      int input = scan.nextInt();
      int count = bitCount(input);
      System.out.printf("%d 의 비트가 가지는 1의 개수: %d", input, count);
      scan.close();

  }

  public static int bitCount(int input) {
      int count = 0;
      int mask = 1 << 31;

      while (true){
          if (mask == 0){
              break;
          }
          if((mask & input) == 0){
              
          }else {
              count++;
          }

          mask = mask >>> 1;
      }

      return count;
  }

}

---

알고리즘 

• 맨 왼쪽 비트를 1로 설정 후 정수와 and 연산. 
• and 연산이 0 이상이라면 마스크의 1 부분은 정수에도 1이 있다는 뜻이기 때문에 카운트를 증가
• 마스크가 0이 될때까지 unsigned right shift (>>>)를 하여 마스크를 오른쪽으로 한칸 이동 후 위 과정 반복 

 

ex. 1을 넣었을 경우

 

1의 개수는 2 (cnt == 2)

 

 

---

사진 정리