#include int bitCount(int m); int numberOfDigits(int d); int explore1(int e1); int explore2(int e2, int n); int main(void){ /*n:ゴール i:手数 j:ゴール直前のマス*/ int n, i = 1, j = 1, t; scanf("%d", &n); /*ゴール直前までの手数を数える*/ do{ if(j + bitCount(j) <= n){ j += bitCount(j); i++; } else{ break; } }while(j < n); /*ゴールに直接行けるマスを求め、出力する*/ if(j == n){ printf("%d\n", i); } else{ t = explore1(n); i++; if(t == -1){ printf("%d\n", -1); } else{ if(explore2(t, n) != j){ do{ if(explore1(t) == -1){ printf("%d\n", -1); break; } else if(explore2(t,n) == j){ i++;; break; } else{ t = explore1(t); i += 2; } }while(0); printf("%d\n", i); } else{ i++; printf("%d\n", i); } } } return 0; } //二進数にしたときの1の数を求める関数 int bitCount(int m){ int i = 1, count = 0; if(m % 2 != 0){ count++; m--; } while(i < m){ i *= 2; } if(i > m){ i /= 2; } while(m > 0){ m -= i; i /= 2; count++; } return count; } //二進数にしたときの桁数を求める関数 int numberOfDigits(int d){ int i = 1, j = 0; while(i < d){ i *= 2; } if(i > d){ i /= 2; } while(i > 0){ i /= 2; j++; } return j; } //nにいけるマスを後ろからさがす関数(nを入れてください) //digits:桁数 t:e1 - iを保存 int explore1(int e1){ int i = 1, digits, t; digits = numberOfDigits(e1); while(i <= digits){ t = e1 - i; if(t + bitCount(t) == e1){ return t; break; } i++; } return -1; } //nにいけるマスにいけるマスを前から探す関数 //digits:桁数 t:e2 - iを保存 n:メイン関数内のnを入れる int explore2(int e2, int n){ int i = 1, digits, t; digits = numberOfDigits(e2); while(i <= digits || t < n){ t = e2 + i; if(t - bitCount(t) == e2){ return t; break; } i++; } return -1; }