数字の最初と最後の桁を入れ替える

次の記事では、ビット演算子を使用して 最初と最後のビットを切り替えることで数値を変更する方法について詳しく説明します。 2 進数またはビット パターンの個々のビットを操作するために使用できる演算子。 ＃＃＃問題文＃＃＃

指定された数値 n について、新しい数値のバイナリ展開の最初と最後のビットが反転されるように数値を変更します。つまり、元のビットが 1 の場合、反転されたビットは 0 になる必要があり、その逆も同様です。最初のビットと最後のビットの間のビットは変更しないでください。

例

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

13 の 2 進展開は 1101 です。

最初と最後のビットを切り替えると、拡張子は 0100 (4 に相当) になります。

したがって、出力結果は 4 になります。

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

27 の 2 進展開は 11011 です。

最初と最後のビットを切り替えると、拡張子は 01010 になり、これは 10 に相当します。

したがって、出力は 10.

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

113 の 2 進展開は 1110001 です。

最初と最後のビットを切り替えると、展開は 0110000 になり、これは 48 に等しくなります。

したがって、出力は 48.

となります。

ソリューションアプローチ

このアプローチでは、ビット単位の XOR と左シフト演算子を使用します。両方のオペランドの対応するビットが異なる場合、ビット単位の XOR 演算子は 1 と評価され、そうでない場合は 0 と評価されます。ビット単位の XOR 演算子の機能を使用します。たとえば、数値 n の最初のビットが 1 の場合、n ^ 1 により数値の最初のビットは 0 になります。さらに、数値の最初のビットが 0 に設定されている場合、この操作はn ^ 1 は 1 に変更します。

数値 n の最初の桁を反転するには、n^1 を計算します。 XOR 演算を実行し、n の最下位ビットまたは最初のビットを 1 に反転します。

最後の桁を反転するには、最後の桁のみを設定して数値 k を生成します。最後のビットの位置 r は log

2

(n) に等しくなります。これは、n の 2 進展開に log

2_{(n) ビットが使用されるためです。 このアプローチを実装するには、次の手順が実行されます −}

n = 1の場合、0を表示してリターンします。

• n と 1 の XOR を計算して、数値の最初のビットを切り替えます。

• n と 1th
• ビットです。
  答えを表示します。

• 予行演習

まず、ビットごとの XOR (^) 演算子がどのように機能するかを理解しましょう。

＃＃＃入力＃＃＃ ＃＃＃フラグ＃＃＃ 入力^フラグ000011101110

	フラグの値が 1 の場合、入力値が反転することがわかります。	数値 57 について考えてみましょう。57 の 2 進展開は 111001 です。

1

1

10010

新しい数字 1 を考えてみましょう。

0

0001 です。 1

最下位ビットまたは左端ビットを切り替えるには、57 ^ 1 を実行します。結果は

1

10002(n) 桁分、1 を左にシフトする必要があります。この場合は log2

数値 111000 が生成されます。

ここで、最後の桁を切り替えるために、最初の桁ではなく最後の桁が設定されるように数値 1 を変更します。これを行うには、log

(57)、つまり 5 です。これを実行すると、次の結果が得られます:

1 0

00000

XOR を計算すると、次の結果が得られます。

1

1000

生成了数字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++程序解决方案以及时间和空间复杂度分析。

以上が数字の最初と最後の桁を入れ替えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。