/*
* Greater NY Regional - Collatz A
* Fred Pickel
*/
#include
#include
#include
typedef unsigned int DWORD;
#define MAX_H_DIG 40
/*
* type1 step (nodd) n->n+1 type2 step (n even) n->(n/2)
* the input value n is a string of bits with most significant bit (MSB) at bit m (0 based)
* if all other bits are 0 (n = 2^m), m steps of type2 get to 1
* Otherwise, suppose the least significant 1 bit is at bit k (0 based)
* then we do k steps of type2 until the LSB is 1
* if the next bit is 0, we do step 1 and step 2 and the LSB is again 1 and we have shift right 1
* if the next bit is not 0, we have j additonal 1 bits, adding 1 (step1) and we have j+1 0 bits
* so do j+1 step 2 to get LSB 1 again
* repeat until we get to 1
* starting with 1..(m-1) 0's 1, we do m-1 (stp1 + step 2 to get to 3 and another 3 steps to 1
* so a total of 2*m+1 steps
* for every 0 bit to the right of the LS 1 bit, subtrat 1 (we only do step2 no step 1)
* for every 1 bit between the MSBit and the LS 1 bit, subtract 1 (since we skip step 1 for the extra 1 bits
* so for MSBit at bit m, count = m for 2^m and
* count = 2*m + 1 - trailing 0 bits - extra 1 bits for everything else
*/
int S(DWORD d)
{
int cnt = 0;
if(d == 0xffffffff) {
return 33;
}
while(d > 1) {
if(d & 1) d++;
else d = d/2;
cnt++;
}
return cnt;
}
int main()
{
DWORD n;
int cnt;
if(scanf("%u",&(n)) != 1){
fprintf(stderr, "scan failed on problem input\n");
return -3;
}
cnt = S(n);
printf("%d\n", cnt);
return 0;
}