資料結構
網路
關係資料庫管理系統 (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)，因為在實現中未使用輔助空間。
結論
本文討論了一種切換數字首位和末位的方法。為此，我們使用了按位左移運算子來生成新的位模式，並使用按位異或運算子來計算結果。為了更深入地理解，我們詳細解釋了該方法的概念、示例的幹執行、使用的演算法、C++程式解決方案以及時間和空間複雜度分析。
581 次瀏覽
