c++:

#include<iostream>
#include<math.h>
using namespace std;

int f(int a, int b){
if( b == 0 )
return 1;
if( b >= 1 )
return a * f(a,b-1);
}

int main(){
long long int a,b,c;
while(cin >> a){
b=0;
for(int i=1;i<log2(a+0.1)+1;i++){
b+=a/f(2,i)*f(2,i-1);
if(a%f(2,i)-f(2,i-1)+1 <= f(2,i-1) && 0 <= a%f(2,i)-f(2,i-1)+1){
b+=a%f(2,i)-f(2,i-1)+1;
}
}
cout << b%1000000000 << endl;
}
return 0;
}