c++でchar型のハミング重みとハミング距離を計算したいです。
ハミング重みとはビット列の中に含まれる1の数で、ハミング距離とは2つのビット列の異なるビットの数です。
例えば
a = 1010
b = 1111
ならば
ハミング重みはa=2,b=4です。
a,bのハミング距離は2です。
もし、これらは配列であれば簡単ですが、char型のまま求めることは可能でしょうか。また、もし直接できなければchar型を2進数の配列に変換することはできますでしょうか。
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
より効率的な方法を知りたければ、上記のサイトを見てみると、いろいろ方法が書いて有ります。
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
蛇足で、ハミング重みを計算する関数(Yuki Inoueさんの書かれたtotal_bits()
)が最近のコンパイラーには実装されています。
なぜ各コンパイラーがこぞってこれらを組み込み関数として用意しているかというと、IntelがCore iシリーズからハミング重みを計算するPOPCNT
命令を追加しているため、これを利用できるようにするためだからです。
C++20でstd::popcount
として提供されるようになりました。