Set all meaningful unset bits of a number

Question

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

`ll x = log2(n) + 1;` -- The program is instantly broken due to you using a floating point function. Second is that [your code should look like this](http://coliru.stacked-crooked.com/a/609f641cebb62044), and not have that competitive coding nonsense in it. — PaulMcKenzie, Jul 21 '22 at 13:41
All this kind of bit twiddling is much easier to understand if you write out values in hex or binary. `std::cout << std::hex << x << '\n';` will tell you much more than writing the value in decimal. — Pete Becker, Jul 21 '22 at 13:51

score 3 · Answer 1 · answered Jul 21 '22 at 13:36

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.

score 1 · Answer 2 · answered Jul 22 '22 at 06:21

You can solve this with shift and or.

uint64_t n = 36757654654;
int i = 1;
while (n & (n + 1) != 0) {
    n |= n >> i;
    i *= 2;
}

Any set bit will be duplicated to the next lower bit, then pairs of bits will be duplicated 2 bits lower, then quads, bytes, shorts, int until all meaningful bits are set and (n + 1) becomes the next power of 2.

Just hardcoding the maximum of 6 shifts and ors might be faster than the loop.

Christophe · Accepted Answer · 2022-07-21T14:21:00.980

0

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.

edited Jul 21 '22 at 14:21

answered Jul 21 '22 at 14:00

Christophe

68,716
7
72
138

1

With c++20 comes https://en.cppreference.com/w/cpp/numeric/countl_zero – Goswin von Brederlow Jul 22 '22 at 06:14
@GoswinvonBrederlow you made my day ! There is even popcount() which before was doomed to be a lot of shifts and ands, or a more subtle byte by byte table driven algorithm, or a non portable implementation dependent function! – Christophe Jul 22 '22 at 07:46
I noticed c++20 has added a bunch of compiler built-ins like that. `__attribute__` is a thing of the past too. Now if only `#pragma once` would get added to the C-Pre-Processor... – Goswin von Brederlow Jul 22 '22 at 17:48

Set all meaningful unset bits of a number

3 Answers3