Concatenate boost :: dynamic_bitset o std :: bitset

Question

¿Cuál es la mejor manera de concatenar 2 bitsets?

Por ejemplo Tengo

boost::dynamic_bitset<> test1(std::string("1111")); 
boost::dynamic_bitset<> test2(std::string("00")); 

deben ser concatenados en un test3 Bitset thrid que a su vez sostiene

111100 

soluciones deben impulsar el uso :: dynamic_bitset. Si la solución funciona con std :: bitset, sería bueno también. Debería haber un enfoque en el rendimiento al concatenar los bits.

ACTUALIZACIÓN: He comparado ambos métodos (stringmethod de mí y Neil y shiftmethod de messenger) y el método de cadena fue mucho más rápido (factor 10 ++). Código aquí: http://pastebin.com/HfpfYfy8

Espero Pastebin está bien para publicar largas listas de códigos. Si hay una mejor manera, contáctame.

Answer 1

Para el bitset estándar, algo como:

#include <bitset> 
#include <string> 
#include <iostream> 
using namespace std; 

template <int N1, int N2 > 
bitset <N1 + N2> concat(const bitset <N1> & b1, const bitset <N2> & b2) { 
    string s1 = b1.to_string(); 
    string s2 = b2.to_string(); 
    return bitset <N1 + N2>(s1 + s2); 
} 

int main() { 
    bitset <4> a(string("1010")); 
    bitset <2> b(string("11")); 
    cout << concat<4,2>(a, b) << endl; 
} 

Answer 2

Para comenzar, añadiré una posible solución por mi cuenta. El siguiente código usa la posibilidad de construir bitsets con std :: string y generar std :: string desde un conjunto de bits.

#include <sstream> // for std::ostringstream 
#include <boost/dynamic_bitset.hpp> 

boost::dynamic_bitset<> test1(std::string("1111")); 
boost::dynamic_bitset<> test2(std::string("00")); 

std::ostringstream bitsetConcat; 
bitsetConcat << test1 << test2; 
boost::dynamic_bitset<> test3(bitsetConcat.str()); 

std::cout << test3 << std::endl; 

Esto funciona, pero tiene que haber otras soluciones, con más prestaciones ...

Actualización:
Gracias a JC Leitão para su edición-sugestión

Answer 3

Aquí hay una puñalada a la solución. No estoy seguro de si se compila.

typedef boost::dynamic_bitset<> Bits; 

Bits Concatenate(const Bits& first, const Bits& second) 
{ 
    Bits value(first); 

    //Increase the size of the bit buffer to fit the data being placed in it 
    value.resize(first.size() + second.size()); 
    value <<= second.size(); 
    value |= second; 
    return value; 
} 

Answer 4

He probado varias soluciones y parece que:

• un buen viejo "bucle" es el más rápido
• bitset es mucho más rápido que dynamic_bitset (no sorprendente), si no se necesita asignación de memoria, la sobrecarga es menor, pero aún existe.
• Puede parecer obvio, pero agregar directamente un conjunto de bits a otro sin crear uno nuevo es más rápido. Esta solución no es adecuada si necesita mantener inalterado el primer conjunto de bits (también obvio).
• Las 3 soluciones no producen el mismo resultado, tienes que hacer un ajuste dependiendo de lo que quieras (ver a continuación).

Aquí está mi código de prueba:

#include <iostream> 
#include <bitset> 
#include <boost/dynamic_bitset/dynamic_bitset.hpp> 
#include "scul/PreciseTimer.h" 

boost::dynamic_bitset<> concatOperatorsDyn(const boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2) 
{ 
    boost::dynamic_bitset<> bs1Copy(bs1); 
    boost::dynamic_bitset<> bs2Copy(bs2); 
    size_t totalSize=bs1.size()+bs2.size(); 
    bs1Copy.resize(totalSize); 
    bs2Copy.resize(totalSize); 
    bs1Copy<<=bs2.size(); 
    bs1Copy|=bs2Copy; 
    return bs1Copy; 
} 

template<size_t sRes,size_t s1,size_t s2> 
std::bitset<sRes> concatString(const std::bitset<s1>& bs1,const std::bitset<s2>& bs2) 
{ 
    std::string s1=bs1.to_string<char,std::char_traits<char>,std::allocator<char> >(); 
    std::string s2=bs2.to_string<char,std::char_traits<char>,std::allocator<char> >(); 

    std::bitset<sRes> res(s1+s2); 
    return res; 
} 

template<size_t sRes,size_t s1,size_t s2> 
std::bitset<sRes> concatLoop(const std::bitset<s1>& bs1,const std::bitset<s2>& bs2) 
{ 
    std::bitset<sRes> res; 
    for(size_t i=0;i<s1;i++) 
     res[i]=bs1[i]; 

    for(size_t i=0;i<s2;i++) 
     res[i+s1]=bs2[i]; 
    return res; 
} 
boost::dynamic_bitset<> concatLoopDyn(const boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2) 
{ 
boost::dynamic_bitset<> res(bs1); 
res.resize(bs1.size()+bs2.size()); 
    size_t bs1Size=bs1.size(); 
    size_t bs2Size=bs2.size(); 

    for(size_t i=0;i<bs2.size();i++) 
     res[i+bs1Size]=bs2[i]; 
    return res; 
} 
boost::dynamic_bitset<> concatStringDyn(const boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2) 
{ 
    std::string s1; 
    std::string s2; 
    to_string(bs1,s1); 
    to_string(bs2,s2); 

    boost::dynamic_bitset<> res(s1+s2); 
    return res; 
} 


template<size_t s1,size_t s2> 
void injectLoop(std::bitset<s1>& bs1,const std::bitset<s2>& bs2,int start=s1-s2) 
{ 
    for(size_t i=0;i<s2;i++) 
     bs1[i+start]=bs2[i]; 
} 


void injectLoopDyn(boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2,int start) 
{ 
    for(size_t i=0;i<bs2.size();i++) 
     bs1[i+start]=bs2[i]; 
} 

void testBitstream() 
{ 
    const std::bitset<20> bs1(std::string("11111111110000000000")); 
    std::bitset<30> bs1Bis(std::string("11111111110000000000")); 
    const std::bitset<10> bs2(std::string("0000011111")); 
    std::bitset<30> bs3; 


    const boost::dynamic_bitset<> bs1D(std::string("11111111110000000000")); 
    boost::dynamic_bitset<> bs1DBis(std::string("11111111110000000000")); 
    bs1DBis.resize(30); 
    const boost::dynamic_bitset<> bs2D(std::string("0000011111")); 
    boost::dynamic_bitset<> bs3D; 

    scul::PreciseTimer t; 
    double d=0.; 

    int nbIter=100; 

    std::cout<<"Bitset concat with strings"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     bs3=concatString<30,20,10>(bs1,bs2); 
    d=t.stop(); 
    std::cout<<bs3.to_string<char,std::char_traits<char>,std::allocator<char> >()<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl;; 


    std::cout<<"Bitset concat with loop"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     bs3=concatLoop<30,20,10>(bs1,bs2); 
    d=t.stop(); 
    std::cout<<bs3.to_string<char,std::char_traits<char>,std::allocator<char> >()<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl; 

    std::cout<<"Bitset inject with loop"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     injectLoop<30,10>(bs1Bis,bs2); 
    d=t.stop(); 
    std::cout<<bs1Bis.to_string<char,std::char_traits<char>,std::allocator<char> >()<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl; 


    std::cout<<"Dynamicbitset concat with loop"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     bs3D=concatLoopDyn(bs1D,bs2D); 
    d=t.stop(); 
    std::string s; 
    to_string(bs3D,s); 
    std::cout<<s<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl; 


    std::cout<<"Dynamicbitset inject with loop"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     injectLoopDyn(bs1DBis,bs2D,20); 
    d=t.stop(); 
    to_string(bs1DBis,s); 
    std::cout<<s<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl; 

    std::cout<<"Dynamicbitset concat with operators"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     bs3D=concatOperatorsDyn(bs1D,bs2D); 
    d=t.stop(); 
    to_string(bs3D,s); 
    std::cout<<s<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl; 


    std::cout<<"Dynamicbitset concat with strings"<<std::endl; 
    t.start(); 
    for(int i=0;i<nbIter;++i) 
     bs3D=concatStringDyn(bs1D,bs2D); 
    d=t.stop(); 
    to_string(bs3D,s); 
    std::cout<<s<<std::endl; 
    std::cout<<"duration="<<d<<std::endl<<std::endl; 

} 

Aquí está la salida llego con VS7.1 en mi equipo:

Bitset concat with strings 
111111111100000000000000011111 
duration=0.000366713 

Bitset concat with loop 
000001111111111111110000000000 
duration=7.99985e-006 

Bitset inject with loop 
000001111111111111110000000000 
duration=2.87995e-006 

Dynamicbitset concat with loop 
000001111111111111110000000000 
duration=0.000132158 

Dynamicbitset inject with loop 
000001111111111111110000000000 
duration=3.19994e-006 

Dynamicbitset concat with operators 
111111111100000000000000011111 
duration=0.000191676 

Dynamicbitset concat with strings 
111111111100000000000000011111 
duration=0.000404152 

se puede observar que la función que escribió usando bucles producir diferentes resultados Es porque escribí entonces para poner el lsb del segundo bitset después del msb del primero (lsb a la derecha).Con la función de cadena o "operador de bit" solo tiene que cambiar los parámetros de llamada.

Answer 5

me hizo una prueba comparando los dos métodos siguientes:

/* ... */ 
    for(int ii = 0; ii < 1000000; ++ii) { 
    std::bitset<16> v1(randomUlongs[ii]); 
    std::bitset<16> v2(randomUlongs[ii+1]); 
#ifdef STRING_TEST 
    std::bitset<32> v3(v1.to_string() + v2.to_string()); 
#else 
    std::bitset<32> v3(v2.to_ulong() | (v1.to_ulong() << 16)); 
    /* print out v3 */ 
    } 

... randomUlongs donde fue constante durante cada ejecución (una gran matriz en una cabecera) para evitar cualquier cosa contaminar resultados. Lo conté con:

~ time for ((ii=0; ii<1000; ii++)); do ./bitset_test >/dev/null; done 

Bajo Linux (x86_i686) con gcc 4.4.6 a nivel de optimización 3: la concatenación de cadenas fue el más rápido, en un factor de 2.

bajo Solaris (SPARC) con gcc 3.4.3 y Sun Studio C++ 5.12 (2011/11/16), ambos con nivel de optimización 3: el enfoque sin cadena fue el más rápido por un factor de 10.

Creo que encontrará que la solución "más rápida" depende en gran medida del compilador, aunque supongo que la plataforma podría desempeñar un papel importante también.