fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. const int MAX = 1e6 + 5;
  8.  
  9. // should be accepted (Fast - I/O)
  10.  
  11. int MSB(ll n)
  12. {
  13.     int msb = -1;
  14.     while (n > 0)
  15.     {
  16.         n = n >> 1;
  17.         msb++;
  18.     }
  19.     return msb;
  20. }
  21.  
  22. void solve()
  23. {
  24.     ll n, x;
  25.     cin >> n >> x;
  26.  
  27.     vector<int> pre(61, 0);
  28.     for (int bit = 0; bit <= 60; bit++)
  29.     {
  30.         bool is_set = ((1LL << bit) & x);
  31.         pre[bit] = is_set;
  32.         if (bit)
  33.         {
  34.             pre[bit] += pre[bit - 1];
  35.         }
  36.     }
  37.  
  38.     ll ans = 0;
  39.     int msb = MSB(n);
  40.  
  41.     for (int bit = msb; bit >= 0; bit--)
  42.     {
  43.         if ((1LL << bit) & n)
  44.         {
  45.             int ones = (bit ? pre[bit - 1] : 0);
  46.             ans += (1LL << (bit - ones));
  47.  
  48.             if ((1LL << bit) & x)
  49.             {
  50.                 break;
  51.             }
  52.         }
  53.     }
  54.  
  55.     ans += ((n & x) == 0);
  56.  
  57.     cout << ans - 1 << endl;
  58. }
  59.  
  60. int main()
  61. {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(NULL);
  64.  
  65.     int t = 1;
  66.     // cin >> t;
  67.  
  68.     while (t--)
  69.     {
  70.         solve();
  71.     }
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7823823864396014592
https://ideone.com/frB8pt
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!