如何在C++中快速比较可变长度位串？

Question

我正在基于二元存在或不存在一组特征来执行对象的比较.这些功能可以用位字符串表示,例如:

10011

该位串具有第一,第四和第五特征.

我正在尝试计算一对位串的相似性,作为两者共有的特征数量.对于给定的一组位串,我知道它们都具有相同的长度,但我不知道在编译时该长度是多少.

例如,这两个字符串有两个共同的特征,所以我希望相似函数返回2:

s(10011,10010) = 2

如何有效地表示和比较C++中的位串？

Answer 1

您可以使用std::bitsetSTL类.

它们可以用位串构建,ANDed,并计数1:

#include <string>
#include <bitset>

int main()
{
  std::bitset<5> option1(std::string("10011")), option2(std::string("10010"));
  std::bitset<5> and_bit = option1 & option2; //bitset will have 1s only on common options
  size_t s = and_bit.count ();                //return the number of 1 in the bitfield
  return 0;
}

编辑

如果在编译时未知位数,则可以使用boost::dynamic_bitset<>:

boost::dynamic_bitset<> option(bit_string);

示例的其他部分不会更改,因为boost::dynamic_bitset<>共享一个公共接口std::bitset.