CODEWITHSUNDEEP
c++boostbit-manipulationboost-multiprecision
user14443912
user14443912

Reputation:

Setting bits on cpp_int

Silly question but, does setting bits on a cpp_int from the boost library work the same as normal numbers?

For instrance, I tried to set some bits on a number like so:

vector<bool> bits; //contains 000000000000011010001100101110110011011001101111
cpp_int M = 0;
int k = 48;
for(bool b : bits) M ^= (-b ^ M) & (1UL << k--);
bits.clear();
bits = toBinary(M); //contains 11001011101100110110011011111

The toBinary(cpp_int&x) method I have gets bits from the number in the simplest way:

  vector<int> toBinary(cpp_int&x) {
    vector<int> bin;

    while (x > 0) {
        bin.push_back(int(x % 2));
        x /= 2;
    }

    reverse(bin.begin(), bin.end());

    return bin;
  }

I can understand losing the 14 zeros in the beginning, what I don't understand is why do lose not 14 but 20 whole bits. I am fairly new to the boost library, so it's most likely a rookie mistake.

Upvotes: 1

Views: 296

Answers (1)

Artyer
Artyer

Reputation: 40801

Probably unsigned long is 32 bit on your system. Thus the first masks generated with (1UL << k--) with k-- being 48 to 32 are not what you expect (it's undefined behaviour).

You can fix this by using a larger type, like unsigned long long, like M ^= (-b ^ M) & (1ULL << k--);.

If you have more than 64 bits, you can probably use cpp_int for more bits, like M ^= (-b ^ M) & (cpp_int(1ULL) << k--);, or a more economical solution like:

cpp_int mask = 1;
mask <<= bits.size();
for (bool b : bits) {
    M ^= (-b ^ M) & mask;
    // Though that can really be `if (b) M |= mask;`
    mask >>= 1;
}

Upvotes: 0

Related Questions