AtCoder / C#でPopCount

PopCountとは

数値を2進数に変換したときに、立っているbitの数を数えることを言います。
例: popcount(12) = 2
12を2進数で表すと1100になりますから、1の数は2つありますので、popcount(12)=2です

最近でいうと、エイシング プログラミング コンテスト 2020のD問題で出てきました。

C＃ではどうやるのか

ちょっと前までは、愚直に、bitにしてstringにして1の数を数えたり、bit演算子を駆使したりしてできました。
参考:ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる

しかし、.Net Core3.0には、ハードウェア命令を直接操作できる関数が導入され、またそれのラッパーとしてBitOperationsというクラスが追加されています。
ただし、これは、CLS準拠ではないので他のコンパイラには含まれていません。

AtCoderのC#(.NET Core 3.1.201)を使うと、.Net Core 3.0で実装された関数を使うことができます。

参考:
System.Runtime.Intrinsics.X86 Namespace
BitOperations クラス

実行例

using System.Numerics;   // ←これが必要です
using System;
public class MainClass
{
    public static void Main()
    {
        // 引数はuint、もしくはulongになるのでint やlongで扱ってるときはキャストする
        Console.WriteLine(BitOperations.PopCount(12));  // 2
        Console.WriteLine(BitOperations.PopCount(100000000));  // 12
        Console.WriteLine(BitOperations.PopCount(2049));  //2
    }
}

AtCoderに提出するときは、コンパイラに『C#(.NET Core 3.1.201)』を選ぶのをわすれないようにしましょう。

他の便利操作

BitOperations.LeadingZeroCount(UInt64)
先頭から0bitの数を数える

BitOperations.TrailingZeroCount(Int64)
末尾から0bitの数を数える