9

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

例えば

a = 1010
b = 1111

ならば

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

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

3 件の回答 3

13

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

#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));

}

出力

a: 2
b: 4
hamming(a,b): 2

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

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

1
  • ありがとうございます。参考にさせていただきます。 Commented 2016年1月23日 8:23
11

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

#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';
}

出力

a  (00001010): 2
b  (00001111): 4
a^b(00000101): 2
10

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

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


C++20でstd::popcountとして提供されるようになりました。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。