Given an integer n(1≤n≤10¹⁸). I need to make all the unset bits in this number as set (i.e. only the bits meaningful for the number, not the padding bits required to fit in an unsigned long long).

My approach: Let the most significant bit be at the position p, then n with all set bits will be 2^{p 1}-1.

My all test cases matched except the one shown below.

Input

288230376151711743

My output

576460752303423487

Expected output

288230376151711743

Code

#include<bits/stdc  .h>
using namespace std;
typedef long long int ll;
 
int main() {
    ll n;
    cin >> n;
    
    ll x = log2(n)   1;
    cout << (1ULL << x) - 1;
    
    return 0;
}

CodePudding user response：

The precision of typical double is only about 15 decimal digits.

The value of log2(288230376151711743) is 57.999999999999999994994646087789191106964114967902921472132432244... (calculated using Wolfram Alpha)

Threfore, this value is rounded to 58 and this result in putting a bit 1 to higher digit than expected.

As a general advice, you should avoid using floating-point values as much as possible when dealing with integer values.

CodePudding user response：

If you need to do integer arithmetics and count bits, you'd better count them properly, and avoid introducing floating point uncertainty:

unsigned x=0;
for (;n;x  )
    n>>=1;
...

(demo)

The good news is that for n<=1E18, x will never reach the number of bits in an unsigned long long. So the rest of you code is not at risk of being UB and you could stick to your minus 1 approach, (although it might in theory not be portable for C before C 20) ;-)

Btw, here are more ways to efficiently find the most significant bit, and the simple log2() is not among them.