Opérations de bits bits et

Table des matières

Un.、Point de connaissance

1.Définition des bits et

2.Applications simples

（1）Détermination de la parité

（2）Prenez les cinq derniers chiffres

   (3)Éliminer les cinq derniers chiffres

（4）2Détermination de la puissance de

 2.、Exercices

1.191. Bits1Nombre de - Boucle de force（LeetCode）

2.Un doigt d'épée. Offer 15. En binaire1Nombre de - Boucle de force（LeetCode）

3. 1356. Selon le binaire numérique 1 Nombre de commandes pour - Boucle de force（LeetCode）

4.762. Calcul des nombres premiers dans la représentation binaire - Boucle de force（LeetCode）

5.231. 2 Puissance - Boucle de force（LeetCode）

 6.397. Remplacement des entiers - Boucle de force（LeetCode）

7.1404. Réduire la représentation binaire à 1 Nombre d'étapes pour - Boucle de force（LeetCode）

---

Un.、Point de connaissance

1.Définition des bits et

  Les bits et les opérateurs ont deux opérandes ,Exprimé en x & y

Calculer chaque bit de l'opérande ,Tous.1Le résultat est1,Sinon0

Opérande gauche	Opérande droit	Résultats
0	0	0
0	1	0
1	0	0
1	1	1

Exemples：0b1010&0b0110=0b0010;（0b Préfixer les nombres binaires ）

（printf Définir les résultats de sortie %dEst un nombre décimal2）

2.Applications simples

（1）Détermination de la parité

if(5%2==1)
{cout<<"5C'est un nombre impair.";}

if(5&1)              //5&1==1
{cout<<"5C'est un nombre impair.";}

if(8&1==0)              
{cout<<"8C'est un nombre pair.";}

Le binaire pair se termine par 0, Le binaire impair se termine par 1.

Nombre pair&1Pour0,Nombre impair&1Pour1,On peut juger..

（2）Prenez les cinq derniers chiffres

//Compte tenu d'un nombre, Trouvez les cinq derniers chiffres de sa représentation binaire , Une sortie décimale suffit .

#include<iostream>
using namespace std;
int main()
{
   int x;
   cin>>x;
   cout<<(x&0b11111)<<endl;

return 0;
}

Le coeur du problème： On a juste besoin des cinq derniers , Le reste n'a pas besoin de , Donc le nombre donné Bits et 0b11111 , De cette façon, on obtient directement les valeurs des cinq derniers chiffres ,Parce que11111 Plus haut 0,Peu importe.0Toujours1 Bits et 0 Tous.0, Peut effacer le haut , Et les cinq derniers ,0&1=0,1&1=1, C'est - à - dire les cinq derniers Bits et 11111 Le résultat est le même , Toujours les cinq derniers. .

 (3)Éliminer les cinq derniers chiffres

Compte tenu d'un32Nombre entier de bits, Demande d'éliminer ses cinq derniers chiffres .

      Éliminer les cinq derniers chiffres , Les cinq derniers deviennent 0, Conserver les bits restants

      Comparez ce nombre à 0b 11111111111111111111111111100000 （Convertir en hexadécimal en0xffffffe0）Bits et.

x&0b11111111111111111111111111100000 Avec x&0xffffffe0 Même chose..

（4）2Détermination de la puissance de

Déterminer si un entier est2Puissance

 Si un nombre est2Puissance, Son binaire doit être 100……00 Forme.(Oui.k- Oui.0） La décimale de ce nombre est

Moins un. ,Le binaire est représenté par011……11Forme（Oui.k- Oui.1）（ Peut être dérivé de la formule de somme d'une série de nombres équivalents ）

Ces deux chiffres correspondent à 0,

Donc un nombre x- Oui.2Puissance,Alorsx&(x-1)Ça doit être0.

(x&(x-1))==0

 2.、Exercices

1.191. Bits1Nombre de - Boucle de force（LeetCode）

class Solution {
public:
    int hammingWeight(uint32_t n) {
       int sum=0;
while(n)
{
n&=(n-1); 
sum++;
}
       return sum; 
    }
};
// Si un nombre se termine par k- Oui.0（ À la fin, il y a 1：100……00）,Soustrayez - le1, Displacement disponible k- Oui.1（Devant.0：011……11）  Les deux bits font k+1- Oui.0, Le chiffre le plus bas du nombre 1Enlevez.
//n & (n-1) Réalisation：Oui.n Le binaire le plus bas de 1Enlevez, Combien de fois? ,C'est tout ce que1.
// Si la fin est 1, Ça diminue. 1,A la fin se trouve0, Les autres chiffres sont les mêmes , Les deux bits et ,1 Toujours effacé, toujours ok n&(n-1)

2.Un doigt d'épée. Offer 15. En binaire1Nombre de - Boucle de force（LeetCode）

Avec1Même chose..

3. 1356. Selon le binaire numérique 1 Nombre de commandes pour - Boucle de force（LeetCode）

Titre：Pour vous donner un tableau entier arr .S'il vous plaît, placez les éléments dans le tableau en nombres dans leur représentation binaire 1 Nombre de commandes ascendantes.

           S'il y a plus d'un binaire numérique 1 Même nombre,Vous devez les trier par ordre croissant de taille numérique.

           Veuillez retourner au tableau trié.
 

class Solution {
public:
int bitcount(int n)   //1Nombre de
{
int sum=0;
while(n)
{
n&=(n-1);
sum++;
}
return sum;
}

vector<int> sortByBits(vector<int>& arr) {

for(int i=0;i<arr.size();i++)
{
arr[i]+=bitcount(arr[i])*100000;   //arr Toutes les valeurs sont mises à jour à   Elle - même + 1Nombre de*100000（Je ne peux pas.10000,Parce que10000%10000Pour0,Tant que c'est plus grand que10^5 Il n'y a qu'un seul 1C'est tout.1000000C'est possible.）, Mettez ce nombre dans l'ordre croissant , C'est la satisfaction. . Le titre est basé sur 1Nombre de commandes pour, Donc le nombre est multiplié par 100000, C'est la première chose à considérer dans le tri , Valeur du BIT le plus élevé ,Et si1 Le même nombre , Et selon la valeur elle - même ,Voilà.  arr[i] + 1Nombre de*100000 C'est - à - dire que les conditions sont remplies.
}

//Créer 「1Nombre de * 100000 + Chiffres originaux」 Pour trier . C'est - à - dire que les chiffres élevés indiquent 1Nombre de, Le chiffre inférieur indique le chiffre original .

sort(arr.begin(),arr.end());   //arrTableau ascendant.

for(int i=0;i<arr.size();i++)
{
arr[i]%=100000;// Enfin, enlevez tous les hauts ,Restearr[i] La valeur initiale .
}
return arr;
    }
};

4.762. Calcul des nombres premiers dans la représentation binaire - Boucle de force（LeetCode）

        Deux entiers. left Et right ,En zone fermée [left, right] Dans le champ d'application,Statistiques et retour à Le nombre de bits de réglage calculés est un nombre premier Nombre entier de .

        Calculer le nombre de bits de réglage C'est dans la représentation binaire 1 Nombre de.

        Par exemple, 21 Représentation binaire de 10101 Oui. 3 Réglage du calcul.

class Solution {
public:

 //Est - ce un nombre premier.
bool isprime(int n)
{
    if(n<2)
    return false;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
return false;
}
return true;
}

 // En chiffres 1Nombre de.Par ici.i Le changement de valeur n'affecte pas forEn boucle,Champ d'applicationleft~rightÀ l'intérieur.iLa valeur de.  Si le Code de cette fonction est écrit dans forÀ l'intérieur,Attention!i La valeur de est modifiée , Une variable intermédiaire doit être initialisée ,Par exemple,mid=i,Pour remplaceriJugementi Si le nombre de est un nombre premier .
int bitcount(int i) 
{
   int num=0;
while(i)
{
    i&=(i-1);
    num++;//numPour1Nombre de.
}
return num;
}

int countPrimeSetBits(int left, int right) {
int sum=0,num;
for(int i=left;i<=right;i++)
{

//JugementnumEst - ce un nombre premier.
if(isprime(bitcount(i))) //Jugement1 Si le nombre de est un nombre premier .
sum++;
}


return sum;
    }
};

5.231. 2 Puissance - Boucle de force（LeetCode）

class Solution {
public:
    bool isPowerOfTwo(int n) {
if(n<=0)
return false;

if((n&(n-1))==0)
return true;

return false;
    }
};

 6.397. Remplacement des entiers - Boucle de force（LeetCode）

Compte tenu d'un entier positif n ,Vous pouvez faire ce qui suit:：

Si n C'est un nombre pair.,Oui. n / 2Remplacer n .
Si n C'est un nombre impair.,Peut être utilisé n + 1Oun - 1Remplacer n .
Retour n Devient 1 Ce qu'il faut Nombre minimum de remplacements .

class Solution {
public:
    int integerReplacement(int n) {
    if(n==1)
    return 0;

    if(n%2==0)
    return 1+integerReplacement(n/2); 
//1Pas,n/=2

    return 2+min(integerReplacement(n/2),integerReplacement(n/2+1)); 
//Deux pas, Parce qu'un nombre impair +1,-1 Après ça, il faut diviser par 2, 
//nLa valeur maximale pour2^31-1,Si+1,Débordement,Alors, d'abordnDivisé par2,Encore.+1,
//floor(n/2)+1 Équivalent à (n+1)/2    floor(n/2) Équivalent à (n-1)/2   floorArrondi vers le bas.
    }
};