时间戳

首页 > 解决方案 > 中间位切换方法

c++ - 中间位切换方法

问题描述

给定一个数字 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;
}

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

标签： c++

解决方案

对于优化的方法，这个问题可能与使用按位运算符有关，这涉及到左移的概念来设置您想要的位和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。

通过将您的数字和位位置（例如）作为输入来实现奇数位的功能，其中您使用at set positionb切换您的数字：^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;
}

推荐阅读