数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学数字的首位和末位比特位切换
以下文章深入解释了使用位运算符通过**切换其首位和末位比特位**来修改数字的方法。位运算符是可以用于操作二进制数或位模式中单个比特位的运算符。
问题陈述
对于给定的数字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)。这是因为log2(n)个比特位用于n的二进制展开。
执行以下步骤来实现此方法：
如果n = 1，显示0并返回。
通过对n与1进行异或运算来切换数字的首位。
通过对n与1 << k进行异或运算来切换数字的末位，其中k是数字的log2(n)th位。
显示答案。
干运行
让我们首先了解按位异或(^)运算符的工作原理。
| 输入 | 标志 | 输入 ^ 标志 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
可以观察到，当标志的值为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 |
生成了数字111000。
现在要切换末位，我们将数字1修改为现在设置末位而不是首位。为此，我们必须将1左移log2(n)位，在本例中为log2(57)，即5。这样做后，我们得到：
| 1 | 0 | 0 | 0 | 0 | 0 |
现在计算异或运算的结果是：
| 0 | 1 | 1 | 0 | 0 | 0 |
生成了数字01100，等于24。将其与原始数字57（其二进制展开为111001）进行比较，可以观察到最终答案中首位和末位已切换。
因此答案是24。
算法
函数**toggle_first_bit()**
计算n ^ 1
更新n
函数**toggle_last_bit()**
初始化r = log2(n)
初始化k = 1 << r
计算n ^ k
更新n
函数**main()**
初始化n
如果(n == 1)
返回0;
函数调用toggle_first_bit()。
函数调用toggle_last_bit()。
显示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)，因为在实现中未使用辅助空间。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
结论
本文讨论了一种切换数字首位和末位的方法。为此，我们使用了按位左移运算符来生成新的位模式，并使用按位异或运算符来计算结果。为了更深入地理解，我们详细解释了该方法的概念、示例的干运行、使用的算法、C++程序解决方案以及时间和空间复杂度分析。
581 次浏览
