C++ 中翻转数字的第一个和最后一个位

给定一个数字 n，翻转数字，使得新数字二进制展开的第一个位和最后一个位相同；也就是说，如果最初分配的位是 1，则翻转的位应分配为 0，反之亦然。介于第一个位和最后一个位之间的元素必须保持不变。位运算符可用于处理二进制数量或位模式中的单个位。

例如

1.

输入 = 12

输出 = 3

说明

12 -> 输入 12 的二进制展开是 1100

翻转二进制数 12 的第一个和最后一个位后，它变为 0011。

0011 -> 3

因此，翻转给定输入的第一个和最后一个位后，输出将是 3。

2.

输入 = 30

输出 = 15

说明

30 -> 输入 30 的二进制展开是 11110。

翻转二进制数 30 的第一个和最后一个位后，它变为 01111。

01111 -> 15

因此，翻转给定输入的第一个和最后一个位后，输出将是 15。

3.

输入 = 145

输出 = 16

说明

145 -> 输入 145 的二进制展开是 10010001

翻转二进制数 145 的第一个和最后一个位后，它变为 00010000。

00010000 -> 16

因此，翻转给定输入的第一个和最后一个位后，输出将是 16。

方法

此方法使用左移运算符和按位异或。如果两个操作数的相应位不同，则按位异或运算符的值为 1，否则为 0。我们将利用按位异或运算符的位切换功能。例如，如果整数 n 的第一个位是 1，则 n ^ 1 将导致第一个位为 0。此外，如果数字的初始位当前设置为 0，则操作 n ^ 1 将其从 0 更改为 1。

我们计算 n ^ 1 来翻转数字 n 的第一个位。为了反转值，它在最低有效位和 n 的第一个位之间执行与 1 的 XOR 操作。我们创建一个数字 k，其中只设置了最后一个位，使用该数字来翻转最后一个位。最后一个位 r 的位置等于 log2(n)。这是因为 n 的二进制展开使用了 log2(n) 位。

算法

1. 首先，读取输入值 n。
2. 应用 XOR 来切换 n 的第一个位：n = n XOR 1。
3. 将值 0 放入计数器变量 pos。
4. 将 n 的值赋给临时变量 temp。
5. 当温度不为零时：将温度向右移动 1%。
   - 将 pos 增加 1。
6. 使用掩码应用 XOR 操作来切换 n 的最后一个位：n = n XOR (1 << (pos - 1))。
7. 输出结果数字 n。

示例 1

让我们用一个 C++ 程序来使用 XOR 切换数字的第一个和最后一个位

输出

说明

1. toggle_first_bit() 函数使用 XOR 操作切换数字的第一个位。
2. toggle_last_bit() 函数查找最后一个数字位置并使用 XOR 切换它。
3. 在“main”函数中，我们将调用 toggle_first_bit 和 toggle_last_bit 函数，分别切换输入数字的第一个和最后一个位。
4. 最后，我们将打印修改后数字的十进制值作为输出。

复杂度分析

时间复杂度

其时间复杂度为 O(1)，因为该方法的操作时间固定，与输入数量无关。

空间复杂度

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