中间位切换方法

Question

给定一个数字 N。我需要以二进制形式切换 N 的中间位并以十进制形式打印结果。

状况：

如果 N 的二进制形式的位数为奇数，则切换中间位（如 111 到 101）。

如果 N 的二进制形式的位数是偶数，则切换两个中间位（如 1111 到 1001）

注意：切换一点意味着将 0 转换为 1，反之亦然。

输入：输入的第一行包含 T 表示测试用例的数量。T 测试用例如下。每个测试用例包含一个数字 N。

输出：对于每个测试用例，在一个新行中，在切换 N 的中间位后打印十进制形式。

约束条件：1 <= T <= 100 1 <= N <= 106

示例： 输入：2 3 5 输出：0 7

测试用例 1：N=3。二进制为 11。切换中间位：00。十进制的 00 为 0。Testcase2：N=5。二进制是 101。切换中间位：111。十进制的 111 是 7。

这是我的方法：我将采用十进制数作为输入并将其转换为二进制，然后根据条件切换位并再次将其转换回二进制。

但是，一旦我将其转换为二进制（为此我使用 32 位大小的数组来保持最大可能）我无法找到切换位的方法..也是由于使用了太多循环，我觉得我的时间复杂度会很糟糕，直到我最终将其转换回十进制形式。

这是我迄今为止尝试过的代码：

#include<iostream>
using namespace std;
int main()
{ int t,i;
  cin>>t; //test cases
  for(i=0;i<t;i++)
  { int n;
    cin>>n;
    //convert to binary logic:
    int binary[32];
    int j=0;
    while(n>0)
    { binary[j]=n%2;
       n=n/2;
       j++;
     }
   // binary number in reverse form is obtained
   // so I create another array to fill it straight:
  int binary_number[32];
  for(l=0,k=j-i;k>=0;k--,l++)
    binary[k]=binary_number[l];
   // binary form of my number gets stored in binary_number
   // unable to proceed after this..

  cout<<endl; // newline after test case finishes

  }
  return 0;
}

有没有更好的方法来解决这个问题？如果可能的话，请帮助我理解一些代码。

Answer 1

对于优化方法，这个问题可以通过使用按位运算符来解决，其中涉及左移的概念来设置所需的位和XOR来处理切换。

要设置任何^第B^个二进制位，您可以<<使用 将十进制数的二进制形式的右位左移1<<(B-1)。切换就像^对需要切换的位使用 XOR 运算符一样简单。

根据您的问题，要求是切换中间位，因此您必须先找到它们。

您需要计算数字中的位数，以确定它是属于第一个还是第二个条件（奇数/偶数）。

为此，您可以实现一个函数，该函数将十进制数作为输入并返回其二进制等效数字的计数：（unsigned用于避免溢出）

unsigned bitCount(unsigned int n)
{
   return (int)log2(n)+1;
}

使用上面的函数来确定位数，如果结果是奇校验，则在c/2+1位置处切换中间位，否则（偶数情况）将中间位设置在c/2+1和c/2位置，考虑说获得的位计数是某个值c。

通过将您的数字和位位置（例如b）作为输入来实现奇数位数的函数，其中您可以使用^at set position切换您的数字b：

int toggle(int n, int b)
{
   return (n^(1<<(b-1)));
}

类似地，通过将​​两个位位置作为参数（除了数字）并根据您的数字在它们的设置位置（通过左移）切换它们来实现偶数位计数的另一个函数：

int toggle2(int n, int b1, int b2)
{
   return ((n^(1<<(b1-1)))^(1<<(b2-1)));
}

不要试图将所有内容都包含在 中main()，而是在需要时通过使用函数使您的代码模块化。您的主要内容应如下所示：

int main()
{ int t; 
  cin>>t;

  while(t--)
 {  unsigned int n; 
    cin>>n;
    int c=bitCount(n);

    if(c%2!=0) // Odd number of digits in your binary number, toggle the mid bit at c/2+1 position.
    cout<<toggle(n, c/2+1);
    else // Even number of digits, toggle the two middle bits at c/2
    cout<<toggle2(n, c/2+1, c/2);

    cout<<"\n"; // Use \n instead of endl since it invokes an unnecessary call to std::flush()
 }
   return 0;
}