Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I increment std::bitset

How can I achieve an increment on a std::bitset<128> in C++?

Because the bitset is 128 bits long, I cannot simply do

std::bitset<128> set = std::bitset<128>();

set = std::bitset<128>(set.to_ulong() + 1ULL);
like image 732
pvorb Avatar asked May 26 '13 16:05

pvorb


2 Answers

The trouble with the code above is in this line in particular:

set = std::bitset<128>(set.to_ulong() + 1ULL);

Unsigned long [ulong] is at least a 32-bit type in C++, depending on the OS + chipset, so in trying to cast a 128-bit variable into a this type you've created a small problem (without an implementation of a larger type, that is).

All is not lost. As @Oli Charlesworth mentioned above, you can use a bigint library, and they are plentiful. A decent one I've used before is here.

For what you're trying to do above, you might try subbing the to_ulong() function in the context of a big integer library, something like to_bigint() which operates on a bitset.

Hope this helps.

like image 33
Cobalt Avatar answered Oct 09 '22 03:10

Cobalt


I'm going to agree with Oli, and say, if you want to do "big-integer" stuff, then you should use big integer library.

However, if you really want to do this using std::bitset, you'll need to do the arithmetic yourself.

template <size_t N>
std::bitset<N> increment ( std::bitset<N> in ) {
//  add 1 to each value, and if it was 1 already, carry the 1 to the next.
    for ( size_t i = 0; i < N; ++i ) {
        if ( in[i] == 0 ) {  // There will be no carry
            in[i] = 1;
            break;
            }
        in[i] = 0;  // This entry was 1; set to zero and carry the 1
        }
    return in;
    }

int main () {
    std::bitset<32> foo;
    std::cout << foo.to_ulong () << ' ';
    foo = increment ( foo );
    std::cout << foo.to_ulong () << ' ';
    foo = increment ( foo );
    std::cout << foo.to_ulong () << ' ';
    foo = increment ( foo );
    std::cout << foo.to_ulong () << std::endl;

    return 0;
}

This prints 0 1 2 3 for me.

like image 183
Marshall Clow Avatar answered Oct 09 '22 05:10

Marshall Clow