By | 19.02.2017

# Find the probability of getting a 1–bit number ?

`Find the probability of getting a 1-bit number after the following procedure is followed:`

`Initially a number x is chosen at random in a given range .After this we again choose a bit from x randomly?`

`Find the expected number of bit 1s if we randomly choose a number x in the given range?`

## Explanation

### Input Format

The first line of input is the number of test cases T. Each test cases is a line contains 2 integers A and B separated by a space.

### Output Format

For each test case output a line containing 2 float numbers separated by a space. The first one is the probability and the second one is the expected number. You should output the number accurate to 5 fractional digits.

### Constraints

1 <= T <= 200

1 <= A <= B <= 10^10

1

2 4

0.61111

1.33333

### Explanation

(10) (11) (100)

(1) So we got a one in :

(1/3)(1/2)+(1/3)(1/1)+(1/3)*(1/3)=(11/18)

(2) The expected 1 we have is

(1)(1/3)+(2)(1/3)+(1)*(1/3)=(4/3)

Time Limit:3.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

SOURCE CODE ::

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

#define mygc(c) (c)=getchar_unlocked()
{
int k,m=0;*x=0;
for(;;)
{
mygc(k);
if(k=='-')
{m=1;
break;
}
if('0'<=k&&k<='9')
{
*x=k-'0';
break;
}
}
for(;;)
{
mygc(k);
if(k<'0'||k>'9')
break;
*x=(*x)*10+k-'0';
}
if(m)(*x)=-(*x);
}

{
int k,m=0;*x=0;
for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}
for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);
}

int T;
ll A, B;

ll cnt(ll A){
ll p, all, rest;
ll res = 0;

for(p=1;;p*=2){
if(A < p) break;
all = (A/(2*p));
rest = (A%(2*p));
res += all * p;
if(rest >= p) res += rest - p;
}

return res;
}

ll cntRange(ll A, ll B){
return cnt(B+1) - cnt(A);
}

int main(){
int i, j, k;
ll st, ed, dig, r, tmp;
double res1, res2;

while(T--){
res1 = res2 = 0;

st = ed = dig = 1;
for(;;){
if(st > B) break;

if(max(st,A) <= min(ed,B)){
tmp = cntRange(max(st,A), min(ed,B));
r = min(ed,B) - max(st,A) + 1;

res1 += tmp / (double)dig;
res2 += tmp;
}

st = st*2;
ed = st*2-1;
dig++;
}

res1 /= (B-A+1);
res2 /= (B-A+1);
printf("%.5f %.5f\n",res1,res2);
}

return 0;
}```

OUTPUT : :

```1

2 4

0.61111

1.33333```