21224


c++でchar型のハミング重みとハミング距離を計算したいです。  
ハミング重みとはビット列の中に含まれる1の数で、ハミング距離とは2つのビット列の異なるビットの数です。

例えば

[code]

    a = 1010
    b = 1111
    
[/code]

ならば

ハミング重みはa=2,b=4です。  
a,bのハミング距離は2です。

もし、これらは配列であれば簡単ですが、char型のまま求めることは可能でしょうか。また、もし直接できなければchar型を2進数の配列に変換することはできますでしょうか。


CC BY-SA 3.0
2016-01-23T08:02:58.867
21223
2021-05-15T14:46:39.893
2016-04-07T17:07:17.687
754
7232
question
c++ c
char型のハミング重みとハミング距離を計算したい。


c 言語の機能だけで実現できます。具体的には、 bitwise 演算を用いて、 bit が立っている個数を計算します。ハミング距離を計算するには、2つの
char の xor 演算を取った結果に対して、 bit の個数を計算します。  
以下の `total_bits` の実装にはいくつも hack っぽい方法があるのですが、解りやすい実装は次です。

[code]

    #include <stdio.h>
    
    
    int total_bits(unsigned char v) {
        unsigned int c; // c accumulates the total bits set in v
    
        for (c = 0; v; v >>= 1) {
            c += v & 1;
        }
        return c;
    }
    
    
    int main() {
        char a = 0x0a;
        char b = 0x0f;
    
        printf("a: %d\n", total_bits(a));
        printf("b: %d\n", total_bits(b));
        printf("hamming(a,b): %d\n", total_bits(a ^ b));
    
    }
    
[/code]

出力

[code]

    a: 2
    b: 4
    hamming(a,b): 2
    
[/code]

* * *

参考: <http://graphics.stanford.edu/~seander/bithacks.html> の counting bitsets

より効率的な方法を知りたければ、上記のサイトを見てみると、いろいろ方法が書いて有ります。


CC BY-SA 3.0
2016-01-23T08:21:25.807
21224
2016-01-23T08:25:39.087
2016-01-23T08:25:39.087
754
754
21223
answer


蛇足で、ハミング重みを計算する関数（Yuki Inoueさんの書かれた`total_bits()`）が最近のコンパイラーには実装されています。

  * [GCC 3.4](https://gcc.gnu.org/gcc-3.4/changes.html)の__builtin_popcount
  * [LLVM 1.5](http://llvm.org/releases/1.5/docs/ReleaseNotes.html)の__builtin_popcount
  * [Visual Studio 2008](http://blogs.msdn.com/b/vcblog/archive/2007/10/18/new-intrinsic-support-in-visual-studio-2008.aspx)の__popcnt

なぜ各コンパイラーがこぞってこれらを組み込み関数として用意しているかというと、IntelがCore
iシリーズからハミング重みを計算する`POPCNT`命令を追加しているため、これを利用できるようにするためだからです。

* * *

C++20で[`std::popcount`](https://cpprefjp.github.io/reference/bit/popcount.html)として提供されるようになりました。


CC BY-SA 4.0
2016-01-23T22:33:46.787
21240
2021-05-15T14:46:39.893
2021-05-15T14:46:39.893
4236
4236
21223
answer


C++の標準ライブラリにはビット集合を扱うクラスstd::bitsetがありますので、それに任せるという選択肢もあります。

[code]

    #include <bitset>
    #include <climits>
    #include <iostream>
    
    int main()
    {
        char a = 0x0a;
        char b = 0x0f;
    
        std::bitset<CHAR_BIT> as(a);
        std::bitset<CHAR_BIT> bs(b);
        std::bitset<CHAR_BIT> as_xor_bs(as ^ bs);
        std::cout << "a  (" << as        << "): " << as.count()        << '\n';
        std::cout << "b  (" << bs        << "): " << bs.count()        << '\n';
        std::cout << "a^b(" << as_xor_bs << "): " << as_xor_bs.count() << '\n';
    }
    
[/code]

出力

[code]

    a  (00001010): 2
    b  (00001111): 4
    a^b(00000101): 2
    
[/code]


CC BY-SA 3.0
2016-01-24T10:47:36.537
21260
2016-01-24T10:47:36.537
7291
21223
answer