C言語で2進数の末尾・先頭のゼロの個数をカウントするプログラム

まずは、2進数における「末尾のゼロ（トレーリングゼロ）」とは何かを理解しましょう。

末尾のゼロ（Trailing Zeros）とは

2進数において、最下位ビット（LSB）側から見て最初に現れる「1」より後ろに続くゼロのことを、末尾のゼロと呼びます。

例

10進数の104を例に考えてみます。

104を2進数に変換すると：（MSB）1101000（LSB）

ここで、

• MSBとは最上位ビット（Most Significant Bit）のことです。
• LSBとは最下位ビット（Least Significant Bit）のことです。
• LSB側から見て最初に「1」が立っているビットより後ろには、ゼロが3つ並んでいます。
• したがって、この数の末尾のゼロは3個です。

末尾のゼロをカウントするプログラム

以下は、入力された数値について、末尾のゼロの個数をカウントするC言語プログラムです。数値を右シフトしながら各ビットを調べ、「1」が現れた時点でループを抜ける仕組みになっています。

#include<stdio.h>
#include<stdlib.h>
int main(){
   int number, i, trail = 0, size;
   printf("Enter a number\n");
   scanf("%d",&number);
   size = sizeof(number) * 8;
   for(i = 0; i < size; i++){
      if((number >> i) & 1) {
         break;
      }
      trail++;
   }
   printf("Number of trailing ZERO is = %d", trail);
   return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

Enter a number
24
Number of trailing ZERO is = 3

入力した24は2進数で「11000」となるため、末尾のゼロが3個であることが確認できます。

先頭のゼロ（Leading Zeros）とは

逆に、最上位ビット側から見て最初に「1」が立つビットよりも前にあるゼロのことを、先頭のゼロと呼びます。

例

10進数の94を例にします。

94を2進数（32ビット整数）で表すと：（MSB）.....001011110（LSB）

この場合、先頭のゼロの個数は25個になります。

先頭のゼロをカウントするプログラム

以下は、入力された数値について、先頭のゼロの個数をカウントするC言語プログラムです。最上位ビットを示すマスクを作成し、数値を左シフトさせながらチェックすることで、「1」が最初に現れる位置を検出しています。

#include<stdio.h>
#include<stdlib.h>
int main(){
   int number, i, lead = 0, Msb,size;
   printf("Enter a number\n");
   scanf("%d",&number);
   size = sizeof(number) * 8;
   Msb=1<<(size-1);
   for(i = 0; i < size; i++){
      if((number << i) & Msb) {
         break;
      }
      lead++;
   }
   printf("Number of Leading ZERO is = %d", lead);
   return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

Enter a number
94
Number of Leading ZERO is = 25