The following article provides an in depth explanation of the method used to modify a number by toggling its first and last bit using bitwise operators. A bitwiseanatoratoris bitwise operator that can be used to manipulate individual bits in binary numbers or bit patterns.
For a given number n, modify the number such that the first and the last bit of the binary expansion of the new number are flipped i.e. if the original bit is 1 then the flipped bitd shvers be 0 and vice versa be 0 and v. bits between the first and the last bit should be left unchanged.
Input: 13
Output: 4
The binary expansion of 13 is 1101.
在切換第一個和最後一個位元之後，擴充變成0100，等於4。
因此，輸出結果為4。
Input: 27
Output: 10
The binary expansion of 27 is 11011.
切換第一個和最後一個位元之後，擴充變成01010，等於10。
Hence the output is 10.
Input: 113
Output: 48
The binary expansion of 113 is 1110001.
On toggling the first and the last bit, the expansion becomes 0110000 which is equal to 48.
Hence the output is 48.
This approach makes use of the bitwise XOR and left shift operator. If the corresponding bit of both operands is different, the bitwise XOR operator evaluates to 1; otherwise, it evaers to 0.' to toggle a bit. For instance, if the first bit of the number, n, is 1, then n ^ 1 will cause the number's first bit to be 0. In addition, if the number's first bit is set to 0, the operation n ^ 1 will change it to 1.
要翻轉數字n的第一個位，我們計算n ^ 1。它執行一個異或操作，將n的最低有效位元或第一個位元與1進行反轉。
為了翻轉最後一位，我們產生一個只有最後一位被設定的數字k。最後一位的位置r等於log2(n)。這是因為在n的二進位展開式中使用了log2(n)位元。
The following steps are performed to implement this approach −
If n = 1, display 0 and return.
Toggle the first bit of the number by taking an XOR of the n with 1.
#透過將n與1<
Display the answer.
#首先讓我們了解位元異或（^）運算子的工作原理。
| Input | Flag | Input ^ Flag |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
可以觀察到，當flag的值為1時，輸入的值會被反轉。
考慮數字57。57的二進位展開式是111001。
| 1 | 1 | 1 | 0 | 0 | 1 |
考慮一個新的數字1。
| 0 | 0 | 0 | 0 | 0 | 1 |
要切換最低有效位或最左邊的位，請執行57 ^ 1，結果為
| 1 | 1 | 1 | 0 | 0 | 0 |
The number 111000 is generated.
現在，為了切換最後一位，我們修改數字1，使得最後一位被設置，而不是第一位。為了做到這一點，我們必須將1左移log2(n)位，或是在這種情況下是log2(57)，也就是5。在這樣做之後，我們得到：
| 1 | 0 | 0 | 0 | 0 | 0 |
Computing XOR now gives us.
| 0 | 1 | 1 | 0 | 0 | 0 |
生成了数字01100，等于24。将其与原始数字57的二进制展开进行比较，可以观察到最终答案中的第一位和最后一位已经被切换。
因此，答案是24。
函数 toggle_first_bit()
Compute n ^ 1
更新 n
函数 toggle_last_bit()
初始化 r = log2(n)
初始化 k = 1 << r
计算 n ^ k
更新 n
Function main()
初始化 n
如果 (n == 1)
return 0;
Function call toggle_first_bit().
调用函数 toggle_last_bit()。
显示 n.
This program modifies an input number n by toggling the first and the last bit of its binary expansion. It employs bitwise operator XOR and left shift operator to achieve its goal.
// 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++程序解决方案以及时间和空间复杂度分析。
以上是切換一個數字的第一個和最後一個位的詳細內容。更多資訊請關注PHP中文網其他相關文章！
