C++ 切换数字的第一个和最后一个比特位

以下文章详细解释了在修改数字时使用按位运算符切换其第一个和最后一个比特位的方法。按位运算符是一种可以用于操作二进制数或位模式中的个别比特的运算符。

问题陈述

对于给定的数字n，修改该数字使得新数字的二进制展开中的第一个和最后一个比特位翻转，即如果原始比特位为1，则翻转后应为0，反之亦然。第一个和最后一个比特位之间的所有比特位应保持不变。

示例

Input: 13

Output: 4

解释

13的二进制展开式是1101。

将第一个和最后一个位进行切换，展开式变为0100，即等于4。

因此输出为4。

Input: 27

Output: 10

解释

27的二进制展开是11011。

通过切换第一个和最后一个位，展开变为01010，即等于10。

因此输出为10。

Input: 113

Output: 48

解释

113的二进制展开是1110001。

在切换第一个和最后一个位之后，展开变为0110000，等于48。

因此输出为48。

解决方案

这种方法利用了位异或和左移运算符。如果两个操作数的相应位不同，位异或运算符的结果为1；否则为0。我们将利用位异或运算符的能力来切换位的值。例如，如果数字n的第一位是1，则n^1将导致数字的第一位变为0。另外，如果数字的第一位设置为0，则操作n^1将将其更改为1。

为了翻转数字n的第一位，我们计算n^1。它对数字n的最低有效位或第一位与1进行异或操作，从而将其值翻转。

为了翻转最后一位，我们生成一个数字k，其中只有最后一位被设置。最后一位的位置r等于log2(n)。这是因为在数字n的二进制展开中使用了log2(n)位。

实施此方法需要执行以下步骤：

• 如果n = 1，则显示0并返回。

• 通过将n与1进行异或，切换数字的第一位。

• 通过将n与1<<k进行异或来切换数字的最后一位，其中k是数字的log2(n)位。

• 显示答案。

演练

让我们首先了解位异或(^)运算符的工作原理。

可以观察到当标志位的值为1时，输入值会被反转。

考虑数字57。57的二进制展开为111001。

考虑一个新的数字 1。

要切换最低有效位或最左边的位，执行 57 ^ 1 的操作，结果为

生成了数字111000。

现在要切换最后一位，我们修改数字1，使最后一位成为设置的位，而不是第一位。为了做到这一点，我们必须将1向左移动log 2 （n）位，或在这种情况下是log 2 （57），基本上是5. 这样做之后我们得到，

计算XOR现在给我们。

生成了01100这个数字，它等于24。将其与原始数字57（二进制展开为111001）进行比较，可以发现最终答案中的第一个和最后一个位已被切换。

因此答案是24。

步骤

函数 切换第一个位()

• 计算 n ^ 1

• 更新 n

函数 切换最后一个位()

• 初始化 r = log2(n)

• 初始化 k = 1 << r

• 计算 n ^ k

• 更新 n

函数 主函数()

• 初始化 n

• 如果 (n 1)

返回 0;

• 调用切换第一个位的函数。

• 调用切换最后一个位的函数。

• 显示 n。

示例：C++程序

该程序通过切换二进制展开的第一个和最后一个位来修改输入数字n。它使用位运算符XOR和左移运算符来实现其目标。

// This C++ program toggles the first and the last bit of a number
#include <iostream>
#include <cmath>
using namespace std;
// this function flips the last bit of the number
// it uses the concept that a log(n) bits are used in the binary expansion of a number n
void toggle_last_bit(int& n){
   int r = log2(n); // value of r indicates the count of last bit of n
   int k; // generate a number with log(n) where only the last bit is 1 using the left shift operator
   k = 1 << r;
   n = n ^ k; // toggle the last bit of n by computing n XOR k
}

// this function flips the first bit of the number by computing n XOR 1
void toggle_first_bit(int& n){
   n = n ^ 1;
}
int main(){
   int n = 113;
   cout << "input number = 113" << endl;
   if(n == 1){
      cout << "0";
      return 0;
   }
   toggle_first_bit(n);  // function call to toggle first bit
   toggle_last_bit(n); // function call to toggle last bit
   cout << "Number after Toggle First and Last Bits of a Number: "<<n;
   return 0;
}

输出

input number = 113
Number after Toggle First and Last Bits of a Number: 48

时间和空间分析

时间复杂度 - O(1)，因为算法始终在常数时间内工作，与输入数字无关。

空间复杂度 - O(1)，因为在实现中没有使用辅助空间。

结论

本文讨论了一种切换数字的第一个和最后一个位的方法。为此，我们使用位左移运算符来生成新的位模式，并使用位异或运算符来计算结果。该方法的概念、示例的详细运行过程、所使用的算法、C++程序解决方案以及时间和空间复杂度分析都被详细解释，以便更深入地理解。