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

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. — schnaader, Mar 11 '11 at 15:23
@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. :) — thomas, Mar 13 '11 at 17:47
`std::vector> 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. :) — raz, May 10 '22 at 14:36

Tristram Gräbener · Answer 1 · 2011-03-11T15:43:02.950

10

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

edited Mar 11 '11 at 15:43

answered Mar 11 '11 at 15:21

Tristram Gräbener

9,601
3
34
50

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! – thomas Mar 11 '11 at 15:28
here you go. I hope I undestood what you wanted. I used 64 as max length, as anyway you're just reading an int – Tristram Gräbener Mar 11 '11 at 15:43
`dynamic_bitset` constructor expects `unsigned long`, not `unsigned long long`: http://www.boost.org/doc/libs/1_46_0/libs/dynamic_bitset/dynamic_bitset.html#cons2 – Cubbi Mar 11 '11 at 15:53

score 6 · Answer 2 · edited Nov 19 '12 at 07:00

6

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/

edited Nov 19 '12 at 07:00

mavam

12,242
10
53
87

answered May 10 '12 at 16:51

vedranm

478
5
6

score 4 · Answer 3 · answered Mar 11 '11 at 15:48

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

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 and 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_bitset.hpp, but how do I link them to my code?? — thomas, Mar 11 '11 at 17:40
@thomas 1. http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-a-bad-practice-in-c 2. You said you were looking into `dynamic_bitset`. Boost is the library that provides it, along with many other useful things. See http://www.boost.org for details. — Cubbi, Mar 13 '11 at 14:18
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! — thomas, Mar 13 '11 at 18:12

score 3 · Answer 4 · answered Mar 11 '11 at 15:21

3

Try using Boost's dynamic_bitset.

answered Mar 11 '11 at 15:21

Steve

1,760
10
18

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 Mar 11 '11 at 15:28
@thomas: The documentation is quite detailed. Have you a specific problem? – Steve Mar 11 '11 at 15:32

score 0 · Answer 5 · answered Oct 31 '15 at 15:21

0

Another solution using std::bitset is to define a large enough bitset, for example bitset<1000>.

Then you can use a variable to control the actual bits and you still can use the member functions of bitset

answered Oct 31 '15 at 15:21

camino

10,085
20
64
115

score -1 · Answer 6 · answered Aug 11 '12 at 13:36

You can do it without using the boost library.

You can dynamically assign the bitset. So instead of

for(x=0;x<binaryNumber.size();x++)
{
    binaryNumber[x]=dec%2;
    dec=dec/2;
}

You can simply do:

 binaryNumber = dec;

Yes it does work!!

Then rather than using a separate vector to store the positions of the 1s, you can do something like this:

for(int i=0;i<binaryNumber.size();i++){
    if(binaryNumber[i])
        cout << "Position of 1: " << i << endl;
}

Hope it helps.

How to implement dynamic bitset in my specific code

6 Answers6