Vertauschen Sie die erste und letzte Ziffer einer Zahl

Der folgende Artikel enthält eine ausführliche Erklärung der Methode zum Ändern einer Zahl durch Umschalten ihres ersten und letzten Bits mithilfe von bitweisen Operatoren. Ein bitweiser Operator ist ein Operator, der zur Manipulation einzelner Bits in Binärzahlen verwendet werden kann oder Bitmuster.

Problemstellung

Ändern Sie für eine gegebene Zahl n die Zahl so, dass das erste und das letzte Bit der Binärentwicklung der neuen Zahl umgedreht werden, d. h. wenn das ursprüngliche Bit 1 ist, sollte das umgedrehte Bit 0 sein und umgekehrt. Alle dazwischen liegenden Bits Das erste und das letzte Bit sollten unverändert bleiben.

Beispiele

Input: 13

Output: 4

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Die binäre Entwicklung von 13 ist 1101.

Nach dem Vertauschen des ersten und letzten Bits wird die Erweiterung zu 0100, was 4 entspricht.

Daher ist das Ausgabeergebnis 4.

Input: 27

Output: 10

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Die binäre Entwicklung von 27 ist 11011.

Nach dem Vertauschen des ersten und letzten Bits wird die Erweiterung zu 01010, was 10 entspricht.

Daher beträgt die Ausgabe 10.

Input: 113

Output: 48

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Die binäre Entwicklung von 113 ist 1110001.

Beim Umschalten des ersten und des letzten Bits wird die Erweiterung zu 0110000, was 48,

entspricht

Daher beträgt die Ausgabe 48,

Lösungsansatz

Dieser Ansatz nutzt den bitweisen XOR- und Linksverschiebungsoperator. Wenn das entsprechende Bit beider Operanden unterschiedlich ist, wird der bitweise XOR-Operator als 1 ausgewertet; andernfalls wird er als 0 ausgewertet. Wir verwenden die Fähigkeit des bitweisen XOR-Operators zum Umschalten ein Bit. Wenn beispielsweise das erste Bit der Zahl n 1 ist, dann führt n ^ 1 dazu, dass das erste Bit der Zahl 0 ist. Wenn außerdem das erste Bit der Zahl auf 0 gesetzt ist, wird die Operation n ^ 1 wird es in 1.

ändern

Um die erste Ziffer einer Zahl n umzudrehen, berechnen wir n^1. Es führt eine XOR-Operation durch und invertiert das niedrigstwertige oder erste Bit von n mit 1.

Um die letzte Ziffer umzudrehen, generieren wir eine Zahl k, bei der nur die letzte Ziffer festgelegt ist. Die Position r des letzten Bits ist gleich log₂(n). Dies liegt daran, dass bei der binären Erweiterung von n log₂(n) Bits verwendet werden.

Die folgenden Schritte werden durchgeführt, um diesen Ansatz umzusetzen −

• Wenn n = 1, 0 anzeigen und zurückgeben.

• Schalten Sie das erste Bit der Zahl um, indem Sie n mit 1.

XOR-verknüpfen

• Tauschen Sie die letzte Ziffer der Zahl aus, indem Sie n mit 1

Zeigen Sie die Antwort an.
Trockenlauf

Lassen Sie uns zunächst verstehen, wie der bitweise XOR-Operator (^) funktioniert.

Eingabe0011Es ist zu beobachten, dass der Eingabewert umgekehrt wird, wenn der Wert des Flags 1 ist.

Flagge	Eingabe ^ Flag
0	0
1	1
0	1
1	0

Betrachten Sie die Zahl 57. Die binäre Entwicklung von 57 ist 111001.

1Betrachten Sie eine neue Nummer 1.

1

1

0

0

1

0Um das niedrigstwertige oder am weitesten links stehende Bit umzuschalten, führen Sie 57^1 aus. Das Ergebnis ist

0

0

0

0

1

1Die Nummer 111000 wird generiert.

1

1

0

0

0

Um nun die letzte Ziffer zu ändern, ändern wir die Zahl 1 so, dass die letzte Ziffer anstelle der ersten gesetzt wird. Dazu müssen wir 1 um log

2

(n) Stellen nach links verschieben, oder in diesem Fall log₂(57), also 5. Danach erhalten wir:

1Computing XOR gibt uns jetzt.

0

0

0

0

0

0

生成了数字01100，等于24。将其与原始数字57的二进制展开进行比较，可以观察到最终答案中的第一位和最后一位已经被切换。

因此，答案是24。

算法

函数 toggle_first_bit()

• Compute n ^ 1

• 更新 n

函数 toggle_last_bit()

• 初始化 r = log2(n)

• 初始化 k = 1

• 计算 n ^ k

• 更新 n

Function main()

• 初始化 n

• 如果 (n == 1)

return 0;

• Function call toggle_first_bit().

• 调用函数 toggle_last_bit()。

• 显示 n.

示例：C++程序

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

Time and Space Analysis

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

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

Conclusion

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

1

1

0

0

0

Das obige ist der detaillierte Inhalt vonVertauschen Sie die erste und letzte Ziffer einer Zahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!