### tom's blog

By tom, history, 5 years ago,
int highest(long long n) {
int r = 0;
while(n) {
r++;
n >>= 1;
}
return r-1;
}

int dfs(long long n) {
if(n == 0) return 0;
int h = highest(n);
long long n1 = n-(1LL<<h);
long long n2 = (1LL<<(h+1))-n;
int res = 1+dfs(n1);
if(n2 < n) res = min(res, 1+dfs(n2));
return res;
}


What is complexity of dfs(n) and why?

• +4

 » 5 years ago, # | ← Rev. 2 →   0 At most log(n) phase n1 will equal to 0. If (n2&(1LL<
 » 5 years ago, # |   +5 I thought so, but it's not true. It's probably something like O(2number of blocks with consecutive 1's), but I can't prove it. DFS(n2) will not be called iff n binary representation is 100...0