How to implement dynamic bitset in my specific code

Question

I am using bitset and to improve the performance of my code I want to change it to dynamic bitset, but after reading some posts related to this, I still don't know the way to define my code.

So I attached my code and I would like to know if any of you could help me giving me some ideas about what should I modify and how.

Thanks in advance :)

// Program that converts a number from decimal to binary and show the positions
// where the bit of the number in binary contains 1

#include <bitset>
#include <iostream>
#include <string>
#include <vector>

using namespace std;


int main()
{

    unsigned long long int dec;
    bitset<5000> binaryNumber;
    bitset<5000> mask;
    mask = 0x1;

    cout << "Write a number in decimal: ";
    cin >> dec;

    // Conversion from decimal to binary
    int x;
    for (x = 0; x < binaryNumber.size(); x++)
    {
        binaryNumber[x] = dec % 2;
        dec = dec / 2;
    }

    cout << "The number " << dec << " in binary is: ";
    for (x = (binaryNumber.size() - 1); x >= 0; x--)
    {
        cout << binaryNumber[x];
    }
    cout << endl;

    // Storage of the position with 1 values
    vector<int> valueTrue;
    for (int r = 0; r < binaryNumber.size(); r++) //
    {
        if (binaryNumber.test(r) & mask.test(r)) // if both of them are bit "1"
                                                 // we store in valueTrue vector
        {
            valueTrue.push_back(r);
        }
        mask = mask << 1;
    }


    int z;
    cout << "Bit 1 are in position: ";
    for (z = 0; z < valueTrue.size(); z++)
    {
        cout << valueTrue.at(z) << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

Solution 1

The easiest way to have a dynamic bitset is to use one ;) http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html

UPDATE : providing a full example

#include<iostream>
#include <boost/dynamic_bitset.hpp>
int main() {
    unsigned long long dec;
    std::cout << "Write a number in decimal: ";
    std::cin >> dec;
    boost::dynamic_bitset<> bs(64, dec);
    std::cout << bs << std::endl;
    for(size_t i = 0; i < 64; i++){
        if(bs[i])
            std::cout << "Position " << i << " is 1" << std::endl;
    }
    //system("pause");
    return 0;
}   

Solution 2

For those who don't use Boost - you can use vector<bool> which is optimized so each element uses only 1 bit.

http://www.cplusplus.com/reference/stl/vector/

Solution 3

Here's your program roughly re-written with dynamic_bitset

#include <iostream>
#include <climits>
#include <string>
#include <boost/lexical_cast.hpp>
#include <boost/dynamic_bitset.hpp>
int main()
{
    std::cout<<"Write a number in decimal: ";
    unsigned long long dec;
    std::cin >> dec;

    // Conversion from decimal to binary
    std::string str;
    for(unsigned long long d = dec; d>0; d/=2)
        str.insert(str.begin(), boost::lexical_cast<char>(d&1) );
    boost::dynamic_bitset<> binaryNumber(str);
    std::cout << "The number " << dec << " in binary is: " << binaryNumber<<'\n';

   // Storage of the position with 1 values
   std::vector<size_t> valueTrue;
   for( size_t pos = binaryNumber.find_first();
        pos != boost::dynamic_bitset<>::npos;
        pos = binaryNumber.find_next(pos))
       valueTrue.push_back(pos);

   std::cout<<"Bit 1 are in position: ";
   for(size_t z=0; z < valueTrue.size(); ++z)
       std::cout << valueTrue[z] << " ";
   std::cout << "\n";
}

test run: https://ideone.com/OdhWE

Note, you cannot immediately construct the bitset from your integer because its constructor expects unsigned long. If you can get by with unsigned longs, the whole conversion loop is unnecessary

Solution 4

Try using Boost's dynamic_bitset.

View more solutions

Comments

[Dijar]

Note that the variable dec you use is 64 bit, so this won't work correctly for larger numbers and the 5000 bits bitset is useless this way. You should store the number in a string instead.

[thomas]

@schnaader. Thanks schnaader. I was thinking about the highest performance variable to the variable dec but I think the only solution will be store dec as a string, as you recommend. So thanks for your entry. :)

[mr_azad]

std::vector<std::bitset<1>> bitset_var; I have this workaround from this problem. Not sure if this would help you. Just put it out there. Might help some in far future. :)

[thomas]

Yeap! This is what I have been looking at, but even with the examples I don't see the way to do it in my code... Could you help me please? Thanks in advance!

[thomas]

Yeap! This is what I have been looking at, even the same link, but even with the examples I don't see the way to do it in my code... Could you help me please? Thanks in advance!

[Steve]

@thomas: The documentation is quite detailed. Have you a specific problem?

[Tristram Gräbener]

here you go. I hope I undestood what you wanted. I used 64 as max length, as anyway you're just reading an int

[Cubbi]

dynamic_bitset constructor expects unsigned long, not unsigned long long: boost.org/doc/libs/1_46_0/libs/dynamic_bitset/…

[thomas]

Wowwwww!! Your programming skills are simply amazing! I've never imagined writing something like this. I hope in the future I am able to do the same. Now I have two doubts. 1.Which are the benefits of using using namespace std; at the beginning of the code or writing std:: when necesary?? 2. I need to link the libraries <boost/lexical_cast.hpp> and <boost/dynamic_bitset.hpp> to run my program. I have found them here: www.boost.org/doc/libs/1_46_0/boost/lexical_cast.hpp and www.boost.org/doc/libs/1_46_0/boost/dynamic_bitset/dynamic_b‌​itset.hpp, but how do I link them to my code??

[Cubbi]

@thomas 1. stackoverflow.com/questions/1452721/… 2. You said you were looking into dynamic_bitset. Boost is the library that provides it, along with many other useful things. See boost.org for details.

[thomas]

One question about the variable dec, declared as unsigned long long. As I want to use it for larger numbers as for example for 5000 bits bitset, I was thinking about declare this variable as string. But I couldn´t make mathematical operations to convert it into binary. What would you recommend me to do? Thanks!