C++，C++/CX に挑戦！

◆ 新版明解C++入門編，新版明解C++中級編での学習。自分なりに要点を整理し、全演習問題を解いて、とりあえず一段落です。
◆ 続いて C# に移行予定でしたが、ここでは、このまま C++、そして C++/CX（UWP）についての記事をアップしていくことにします。
◆ C# については別のブログで初歩の初歩から学習を進めたいと思います。準備ができたらリンクを貼りますので、よろしくお願いします。

2017年11月17日

《その135》「 1 」であるビットを数える

　「 1 」であるビットを数える

　整数内の「 1 」であるビットを数えるプログラムです。

　関数 int count_bits(Type x) が「 1 」であるビットを数えます。
①と②の２種類ありますが、両方とも同じ働きをします。

【 ①の関数】
　仮引数として受け取った整数 x を、右に 1ビットずつシフトしながら整数 1 との論理積を調べます。
論理積が 0 になったら、x の「 1 」が無くなったことになるので、そこでカウント終了です。

【 ②の関数】
　x &= x - 1; の操作で x の一番右にある「 1 」が消えることを利用しています。


    x     00101100 ←「 1 」が 3個
&)  x-1   00101011
------------------
          00101000 ←「 1 」が 2個になった。

x が 0 になるまでの操作回数が「 1 」の個数ということになります。

　また、関数 char* bits_of(Type x) は "101･･･100"の形式の文字列を作ります。
両関数とも関数テンプレートにしてあるので、型が異なっていても受け取ってくれます。


#include <iostream>
using namespace std;

template <class Type>
char* bits_of(Type x) {
    int n = numeric_limits<Type>::digits;
    char* vec = new char[n + 1];

    for (int i = 0; i < n; i++) {
        if ((x >> i) & 1U) vec[n - i - 1] = '1';
        else               vec[n - i - 1] = '0';
    }
    vec[n] = '\0';
    return vec;
}

template <class Type>
int count_bits(Type x) {        // ①
    int bits = 0;
    while (x) {
        if (x & (Type)1) bits++;
        x >>= 1;
    }
    return bits;
}

/*
template <class Type>
int count_bits(Type x) {        // ②
    int bits = 0;
    while (x) {
        x &= x - 1;
        bits++;
    }
    return bits;
}
*/

int main() {
    cout << "unsigned long\n";
    unsigned long a = 123456;
    cout << bits_of(a) << "  " << a << '\n';
    cout << "1 であるビットの数 : " << count_bits(a) << "\n\n";

    cout << "unsigned short\n";
    unsigned short b = ~0;
    cout << bits_of(b) << "  " << b << '\n';
    cout << "1 であるビットの数 : " << count_bits(b) << "\n\n";

    cout << "unsigned int\n";
    unsigned int c = 2863311530;
    cout << bits_of(c) << "  " << c << '\n';
    cout << "1 であるビットの数 : " << count_bits(c) << '\n';
}