I was recently solving this problem on Codeforces titled Bits. It was a fairly interesting problem considering a few new learnings I had.

To be simply put, the aim of the problem is to get the number with the maximum number of bits (popcount(x)) within the range [l, r].

Approach

The problem can be approached as follows.

For any given number from 1 to n, the maximum number of bits will be in a number of the form 2^b - 1, or in other words, a number one less than power of two. For instance, for n = 8 (binary: 1000), the maximum number of bits are in the number 7 (binary: 111).

But is this always possible? The answer is no because the range of numbers [l ,r] does not start from 1 and it is possible that no power of 2 exists in the given range of numbers.

To solve this case, the starting approach can be extended to work in a recursive manner by bringing down the problem size to current number of bits - 1.

For instance, consider the range [9, 14]. Writing all the numbers in binary form

9   = 1001
10  = 1010
11  = 1011
12  = 1100
13  = 1101
14  = 1110

There exists no power of two in the given range (i.e. no number with only the most significant bit set) and the problem can be reduced to solving for the range [1, 6].

1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110

If you observe, this is simply dropping the first bit and solving a smaller sub-problem. We keep stripping down the most significant bit until we find a range where a power of two exists. Removing the most significant bit is as simple as 2^b - n, where b is the number of bits in n.

This range fortunately has a largest power of two as 4 and hence the maximum number of bits are in the number 3 (binary: 011). Now adding the bit back, final answer is 11 (binary: 1011).

Solution

Here is the solution in C++14.

#include <bits/stdc++.h>
using namespace std;

// types
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef map<string, ll> msl;
typedef map<ll, ll> mll;
typedef set<int> sl;
typedef set<string> ss;
typedef pair<ll,ll> pll;

// helpers
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define I insert
#define E erase
#define L length()
#define SZ size()

// count number of bits in "n"
ll bitc(ll n) {
  ll c = 0;
  while (n) {
    ++c;
    n /= 2;
  }
  return c;
}

ll solve(ll l, ll r) {
  if (l == r) {
    return l;
  }

  // find largest power of 2 <= r
  ll bcr = bitc(r);
  ll p2r = 1LL << (bcr - 1LL);

  // if no power of two in the range, solve for one less bit and add the bit to the final result
  if (p2r <= l) {
    return solve(l - p2r, r - p2r) + p2r;
  }

  // the next two conditions help identify the largest power of two available in range

  // if (largest power of two - 1) in range
  ll mp2r = 1LL << bcr;
  if (mp2r - 1LL <= r) {
    return mp2r;
  }

  // p2r > l after above conditions fail
  return p2r - 1LL;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  ll n; cin >> n;
  while (n--) {
    ll l, r; cin >> l >> r;
    cout << solve(l, r) << endl;
  }

  return 0;
}

Learnings

One small thing that one could miss out is implicit type-casting of constants in C++. If you write 1 << n and n > 32, this will cause an integer overflow and wrap around because all constants have datatype as 32-bit integer (int) by default. To explicitly tell the compiler, one should suffix it with the LL identifier. This caused me two wrong submissions unfortunately.

Updates and Corrections

If you see mistakes or want to suggest changes, please create issues or revisions against source.