fork(11) download 
  1. #include <algorithm>
  2. #include <ctime>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. const unsigned ALL_ONES = (unsigned)-1;
  7.  
  8. int czeros_fast(unsigned Q) {
  9.     if (Q == 0) return 8*sizeof(Q);
  10.     if (Q == ALL_ONES) return 0;
  11.     unsigned state = Q | Q<<1 | 1;
  12.     int steps = 1;
  13.     if (state == ALL_ONES) return 1;
  14.     while (true) {
  15.         unsigned new_state = state | state<<steps;
  16.         if (new_state == ALL_ONES) break;
  17.         state = new_state;
  18.         steps *= 2;
  19.     }
  20.     int lo = steps, hi = 2*steps;
  21.     while (hi-lo > 1) {
  22.         int med = lo+(hi-lo)/2;
  23.         unsigned med_state = state | state<<(med-steps);
  24.         if (med_state == ALL_ONES) hi = med; else lo = med;
  25.     }
  26.     return hi;
  27. }
  28.  
  29. int main() {
  30.     time_t tstart;
  31.     unsigned Q;
  32.     long long total;
  33.  
  34.     tstart = clock();
  35.     Q = 0;
  36.     total = 0;
  37.     do { total += czeros_fast(Q); ++Q; } while (Q < 123456789);
  38.     cout << "fast: " << total << " " << double(clock()-tstart)/CLOCKS_PER_SEC << endl;
  39. }
Success #stdin #stdout 2.2s 3296KB
comments (?)
stdin 
Standard input is empty
stdout 
fast: 776400680 2.2
https://ideone.com/unp7hD
language:
C++14 (gcc 8.3)
created:
11 years 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!