2017年2月14日火曜日

バイナリ数値2進数にある1の数をカウントするプログラム

単純に1ビットずつビットマスクして計算するのもわかりやすいが
ビットカウントする計算式があるのでサンプルコードを書いておきます。





//1の数を数える
static int bitCount(ushort value)
{
    value = (ushort)(value - ((value %gt;%gt; 1) & 0x5555));
    value = (ushort)((value & 0x3333) + ((value %gt;%gt; 2) & 0x3333));
    value = (ushort)((value + (value %gt;%gt; 4)) & 0x0f0f);
    value = (ushort)(value + (value %gt;%gt; 8));
    return value & 0x1f;
}

static List%lt;int%gt; counts = new List%lt;int%gt;()
{
    0,//0
    1,//1
    1,//2
    2,//3
    1,//4
    2,//5
    2,//6
    3,//7
    1,//8
    2,//9
    2,//A   1010
    3,//B   1011
    2,//C   1100
    3,//D   1101
    3,//E
    4,//F
};


static void Main(string[] args)
{


    for (int i = 0x0; i %lt;= 0xffff; i++)
    {
        var a = bitCount((ushort)i);
        var b = counts[(i %gt;%gt; 12) & 0xf] + counts[(i %gt;%gt; 8) & 0xf] + counts[(i %gt;%gt; 4) & 0xf] + counts[i & 0xf];
        if (a != b) throw new Exception(i.ToString());
    }
}

Androider