Changer le premier et le dernier chiffre d'un numéro

L'article suivant fournit une explication détaillée de la méthode utilisée pour modifier un nombre en basculant son premier et son dernier bit à l'aide d'opérateurs au niveau du bit Un opérateur au niveau du bit est un opérateur qui peut être utilisé pour manipuler des bits individuels dans des nombres binaires. ou des modèles de bits.

Énoncé du problème

Pour un nombre n donné, modifiez le nombre de telle sorte que le premier et le dernier bit de l'expansion binaire du nouveau nombre soient inversés, c'est-à-dire que si le bit d'origine est 1, alors le bit inversé doit être 0 et vice versa. le premier et le dernier bit doivent rester inchangés.

Exemples

Input: 13

Output: 4

La traduction chinoise de

Explication

est :

Explication

Le développement binaire de 13 est 1101.

Après avoir commuté le premier et le dernier bits, l'extension devient 0100, ce qui est égal à 4.

Par conséquent, le résultat de sortie est 4.

Input: 27

Output: 10

La traduction chinoise de

Explication

est :

Explication

Le développement binaire de 27 est 11011.

Après avoir commuté le premier et le dernier bits, l'extension devient 01010, ce qui est égal à 10.

Le résultat est donc 10.

Input: 113

Output: 48

La traduction chinoise de

Explication

est :

Explication

Le développement binaire de 113 est 1110001.

En basculant le premier et le dernier bit, l'expansion devient 0110000, ce qui équivaut à 48.

D'où la sortie est de 48.

Approche de la solution

Cette approche utilise l'opérateur XOR au niveau du bit et l'opérateur de décalage gauche. Si le bit correspondant des deux opérandes est différent, l'opérateur XOR au niveau du bit est évalué à 1 ; sinon, il est évalué à 0. Nous utiliserons la capacité de basculement de l'opérateur XOR au niveau du bit. un bit. Par exemple, si le premier bit du nombre, n, est 1, alors n ^ 1 fera que le premier bit du nombre sera 0. De plus, si le premier bit du nombre est défini sur 0, l'opération n ^ 1 le changera en 1.

Pour retourner le premier chiffre d'un nombre n, on calcule n^1. Il effectue une opération XOR, en inversant le bit le moins significatif ou le premier bit de n avec 1.

Pour retourner le dernier chiffre, nous générons un nombre k avec uniquement le dernier chiffre défini. La position r du dernier bit est égale à log₂(n). En effet, log₂(n) bits sont utilisés dans le développement binaire de n.

Les étapes suivantes sont effectuées pour mettre en œuvre cette approche −

• Si n = 1, affichez 0 et revenez.

• Basculez le premier bit du nombre en prenant un XOR du n avec 1.

• Changez le dernier chiffre du nombre en XORing n avec 1ième chiffre du nombre.

• Affichez la réponse.

Fonctionnement à sec

Commençons par comprendre comment fonctionne l'opérateur XOR au niveau du bit (^).

Entrée	Drapeau	Entrée ^ Drapeau
0	0	0
0	1	1
1	0	1
1	1	0

On peut observer que lorsque la valeur du drapeau est 1, la valeur d'entrée sera inversée.

Considérez le nombre 57. Le développement binaire de 57 est 111001.

1

1

1

0

0

1

Considérez un nouveau numéro 1.

0

0

0

0

0

1

Pour basculer le bit le moins significatif ou le plus à gauche, faites 57^1, le résultat est

1

1

1

0

0

0

Le nombre 111000 est généré.

Maintenant, pour changer le dernier chiffre, nous modifions le chiffre 1 pour que le dernier chiffre soit défini à la place du premier. Pour ce faire, nous devons décaler 1 vers la gauche de log₂(n) places, ou dans ce cas log₂(57), ce qui vaut 5. Après avoir fait cela, nous obtenons :

1

0

0

0

0

0

Le calcul XOR nous donne maintenant.

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

• 计算 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++程序解决方案以及时间和空间复杂度分析。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!