【Java】整数のセットビット（1のビット）を数えるプログラム

整数に含まれるセットビット（値が「1」になっているビット）の個数を数えることは、ビット演算における基本的な問題のひとつです。この記事では、Brian Kernighan（ブライアン・カーニハン）のアルゴリズムを用いて、効率的にセットビットをカウントする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

10進数の「11」は2進数で表すと 1011 となり、「1」のビットが3つ含まれているため、実行結果は3と表示されます。

Brian Kernighanのアルゴリズムの仕組み

上記のコードは、Brian Kernighanのアルゴリズムによる実装です。Demoクラスには、静的メソッド set_bits_count が定義されており、引数として受け取った整数に含まれるセットビットの数を返します。

このアルゴリズムの鍵となるのが、num &= (num - 1) というビット演算です。「ある数」と「その数から1を引いた数」の論理積（AND）を取ると、元の数の最下位にあるセットビットが必ず消去されるという性質があります。

例えば、11 (1011) & 10 (1010) = 1010、次に 1010 & 1001 = 1000、さらに 1000 & 0111 = 0000 となり、3回の演算で数が0になります。つまり、ループが1回回るごとにセットビットが1つずつ取り除かれていくため、変数 count をインクリメントしながら num が0になるまで繰り返せば、その回数がそのままセットビットの総数になります。

コードの流れ

set_bits_count メソッドでは、まずカウント用の変数 count を0で初期化します。続いて、num が0より大きい間、num と num - 1 のAND演算を num に代入し、そのたびに count を1つ増やします。num が0になった時点でループを抜け、累積された count の値を呼び出し元へ返します。

main メソッドでは、セットビットを調べたい対象の整数（ここでは11）を定義し、それを引数として set_bits_count メソッドを呼び出しています。計算結果は、説明用のメッセージとともにコンソールへ出力されます。

計算量について

単純に全ビットを順番に確認する方式では、ビット幅（int型なら最大32回）分のループが必要ですが、このアルゴリズムではセットビットの数だけループが実行されます。そのため、セットビットが少ない数値に対しては非常に効率的であり、計算量は O(k)（kはセットビットの個数）となります。