Tăng liên kết :: dynamic_bitset hoặc std :: bitset

Question

cách tốt nhất để ghép 2 bits là gì?

Ví dụ tôi đã có

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

họ nên được nối vào một Test3 BitSet thrid mà sau đó giữ

111100 

Solutions nên sử dụng tăng :: dynamic_bitset. Nếu các giải pháp làm việc với std :: bitset, nó sẽ được tốt đẹp quá. Nên tập trung vào hiệu suất khi ghép các bit.

CẬP NHẬT: Tôi đã so sánh cả hai phương pháp (stringmethod từ tôi và Neil và shiftmethod từ messenger) và stringmethod nhanh hơn rất nhiều (hệ số 10 ++). Mã số tại đây: http://pastebin.com/HfpfYfy8

Tôi hy vọng Pastebin sẽ được chấp thuận để đăng danh sách mã dài. Nếu có cách nào tốt hơn, vui lòng liên hệ với tôi.

Answer 1

Đối với bitset tiêu chuẩn, một cái gì đó như:

#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

Để bắt đầu, tôi sẽ tự mình thêm một giải pháp có thể. Đoạn mã sau sử dụng khả năng xây dựng các bit với chuỗi std :: và tạo ra một chuỗi std :: từ một bitet.

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

này hoạt động, nhưng phải có khác, giải pháp performant thêm ...

Cập nhật:
Nhờ JC Leitão cho mình chỉnh sửa-gợi ý

Answer 3

Đây là cú đâm vào một giải pháp. Không chắc chắn nếu nó biên dịch.

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

tôi đã thử nghiệm một số giải pháp và có vẻ như rằng:

• một tốt cũ "cho vòng lặp" là nhanh nhất
• bitset được nhanh hơn rất nhiều so với dynamic_bitset (không đáng ngạc nhiên), nếu không cần phân bổ bộ nhớ, chi phí thấp hơn nhưng vẫn tồn tại.
• Điều này có vẻ hiển nhiên nhưng trực tiếp nối một bitet với nhau mà không cần tạo bitet mới nhanh hơn. Giải pháp này không phù hợp nếu bạn cần giữ bitet đầu tiên không thay đổi (hiển nhiên).
• 3 giải pháp không tạo ra kết quả tương tự, bạn phải thực hiện một số điều chỉnh tùy theo ý muốn bạn muốn (xem bên dưới).

Đây là mã thử nghiệm của tôi:

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

} 

Đây là kết quả tôi nhận được với VS7.1 trên máy tính của tôi:

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 

Bạn có thể nhận thấy rằng các chức năng tôi đã viết bằng vòng tạo ra các kết quả khác nhau. Đó là bởi vì tôi đã viết sau đó để đặt lsb của bitet thứ hai sau khi msb của một trong những đầu tiên (lsb bên phải).Với chuỗi hoặc "toán tử bit", bạn chỉ cần chuyển đổi các tham số gọi.

Answer 5

Tôi chạy một thử nghiệm so sánh hai phương pháp sau đây:

/* ... */ 
    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 */ 
    } 

... nơi randomUlongs là không đổi trong mỗi lần chạy (một mảng lớn trong một tiêu đề) để tránh kết quả bất cứ điều gì gây bệnh. Tôi hẹn giờ nó với:

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

Dưới Linux (x86_i686) với gcc 4.4.6 ở mức tối ưu hóa 3: chuỗi nối là nhanh nhất, với hệ số 2.

Dưới Solaris (sparc) với gcc 3.4.3 và Sun Studio C++ 5.12 (2011/11/16), cả hai với mức tối ưu 3: cách tiếp cận không phải chuỗi nhanh nhất theo hệ số 10.

Tôi nghĩ bạn sẽ thấy giải pháp "nhanh nhất" phụ thuộc nhiều vào trình biên dịch, mặc dù tôi cho rằng nền tảng có thể đóng vai trò quan trọng cũng.