Flip the Bits（思维）

You are given a positive integer n. Your task is to build a number m by flipping the minimum number of bits in the binary representation of n such that m is less than n (m < n) and it is as maximal as possible. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 10⁵) specifying the number of test cases.

Each test case consists of a single line containing one integer n (1 ≤ n ≤ 10⁹), as described in the statement above.

Output

For each test case, print a single line containing the minimum number of bits you need to flip in the binary representation of n to build the number m.

Example

Input

2
5
10

Output

1
2

题目意思：将一个2进制的n中每个位翻转得到一个比n小且尽可能大的数，求输出翻转了几位。 

解题思路：这道题该由我背锅，我当时先是翻译错了题意，后来稍微有一点眉目了，我又理解错了那个flip的意思，这里面的翻转并不是那种交换(swap那样的），而是像硬币正面换到反面那样的翻转，也就
是0与1的交换，根据题意可以推出想要得到一个既要比n小还有尽可能大的数，只有是n前面的那一个数n-1。所以就是根据n构造一个二进制的n-1,方法就是找到n的二进制中最后面的那一个1翻转为0，而最
后一个1之后的0全都翻转成1，统计所用的翻转次数即可。

 #include<cstdio>

 #include<cstring>

 int main()

 {

     int t,n,j,k,i,count;

     int a[];

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         memset(a,-,sizeof(a));

         j=;

         count=;

         i=n;

         while(i)

         {

             a[j]=i%;

             if(a[j]==)

             {

                 count++;

             }

              if(a[j]==)

              {

                  count++;

                  break;

              }

             i/=;

             j++;

         }

         printf("%d\n",count);

     }

     return ;

 }

巴特西

Flip the Bits（思维）

最新文章

热门文章