比特運算比特與

目錄

一、知識點

1.比特與的定義

2.簡單應用

（1）奇偶性判定

（2）取末五比特

   (3)消除末尾五比特

（4）2的幂判定

 二、習題

1.191. 比特1的個數 - 力扣（LeetCode）

2.劍指 Offer 15. 二進制中1的個數 - 力扣（LeetCode）

3. 1356. 根據數字二進制下 1 的數目排序 - 力扣（LeetCode）

4.762. 二進制錶示中質數個計算置比特 - 力扣（LeetCode）

5.231. 2 的幂 - 力扣（LeetCode）

 6.397. 整數替換 - 力扣（LeetCode）

7.1404. 將二進制錶示减到 1 的步驟數 - 力扣（LeetCode）

---

一、知識點

1.比特與的定義

 比特與運算符有兩個操作數，錶示為 x & y

對操作數的每一比特進行運算，都是1的時候結果為1，否則為0

左操作數	右操作數	結果
0	0	0
0	1	0
1	0	0
1	1	1

舉例：0b1010&0b0110=0b0010；（0b為二進制數前綴）

（printf設置輸出結果%d為十進制數2）

2.簡單應用

（1）奇偶性判定

if(5%2==1)
{cout<<"5是奇數";}

if(5&1)              //5&1==1
{cout<<"5是奇數";}

if(8&1==0)              
{cout<<"8是偶數";}

偶數二進制末比特為0，奇數二進制末比特為1。

偶數&1為0，奇數&1為1，即可判斷。

（2）取末五比特

//給定一個數，求它的二進制錶示的末五比特，以十進制輸出即可。

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

return 0;
}

問題核心：我們只需要末五比特，剩下的比特不需要，所以將給定的數 比特與 0b11111 ，這樣可以直接得到末五比特的值，因為11111再高比特為0，不管是0還是1 比特與 0 都是0， 即可將高比特抹去，而末五比特，0&1=0，1&1=1，也就是說末五比特 比特與 11111的結果是不變的，仍然是末五比特。

 (3)消除末尾五比特

給定一個32比特整數，要求消除它的末五比特。

      消除末五比特，即將末五比特變成0，保留剩下的比特

      將這個數與0b 11111111111111111111111111100000 （轉換成十六進制為0xffffffe0）比特與。

x&0b11111111111111111111111111100000 與 x&0xffffffe0 同理。

（4）2的幂判定

判斷一個整數是不是2的幂

 如果一個數是2的幂，它的二進制必然為 100……00 形式。(有k個0）這個數的十進制為

將其减一，二進制錶示為011……11形式（有k個1）（可根據等比數列的和的公式來推導）

這兩個數比特與為0，

所以一個數x是2的幂，那麼x&(x-1)必然為0。

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

 二、習題

1.191. 比特1的個數 - 力扣（LeetCode）

class Solution {
public:
    int hammingWeight(uint32_t n) {
       int sum=0;
while(n)
{
n&=(n-1); 
sum++;
}
       return sum; 
    }
};
//若一個數末尾有k個0（末尾的前面是1：100……00），將它减1，錯比特可得k個1（前面為0：011……11） 兩者比特運算得到k+1個0，將數的最低比特1去掉。
//n & (n-1) 實現：將n的二進制最低比特的1去掉，去掉多少次，就有多少1。
//若末尾為1，它减1，末尾為0，其他比特數一樣，兩者比特與，1仍然消去仍然可以n&(n-1)

2.劍指 Offer 15. 二進制中1的個數 - 力扣（LeetCode）

與1同理。

3. 1356. 根據數字二進制下 1 的數目排序 - 力扣（LeetCode）

題目：給你一個整數數組 arr 。請你將數組中的元素按照其二進制錶示中數字 1 的數目昇序排序。

           如果存在多個數字二進制中 1 的數目相同，則必須將它們按照數值大小昇序排列。

           請你返回排序後的數組。
 

class Solution {
public:
int bitcount(int n)   //1的數目
{
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裏所有數值更新為  它本身 + 1的數目*100000（不能是10000，因為10000%10000為0，只要是大於10^5的數裏面只有一個1就行1000000也可以），給這個數昇序，即滿足題意。題目先根據1的數目排序，所以數目乘以100000，這個是排序第一個要考慮的，最高比特的值，然後若1的數目一樣，再根據數值本身，這樣  arr[i] + 1的數目*100000 即滿足條件。
}

//造出 「1的個數 * 100000 + 原數字」的數字來排序。即高比特數字錶示1的個數，低比特數字錶示原數字。

sort(arr.begin(),arr.end());   //arr數組昇序。

for(int i=0;i<arr.size();i++)
{
arr[i]%=100000;//最後將高比特都去掉，留下arr[i]最初本身的數值。
}
return arr;
    }
};

4.762. 二進制錶示中質數個計算置比特 - 力扣（LeetCode）

        給你兩個整數 left 和 right ，在閉區間 [left, right] 範圍內，統計並返回 計算置比特比特數為質數 的整數個數。

        計算置比特比特數 就是二進制錶示中 1 的個數。

        例如， 21 的二進制錶示 10101 有 3 個計算置比特。

class Solution {
public:

 //是否為質數。
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;
}

 //數比特中1的個數。這裏面i數值的改變不影響for循環裏，範圍在left~right裏的i的數值。 這個函數的代碼若寫在for裏面，一定要注意i的值是改變的，應該要初始化一個中間變量，比如mid=i，來代替i判斷i的個數是否為質數。
int bitcount(int i) 
{
   int num=0;
while(i)
{
    i&=(i-1);
    num++;//num為1的個數。
}
return num;
}

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

//判斷num是否為質數。
if(isprime(bitcount(i))) //判斷1的個數是否為質數。
sum++;
}


return sum;
    }
};

5.231. 2 的幂 - 力扣（LeetCode）

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

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

return false;
    }
};

 6.397. 整數替換 - 力扣（LeetCode）

給定一個正整數 n ，你可以做如下操作：

如果 n 是偶數，則用 n / 2替換 n 。
如果 n 是奇數，則可以用 n + 1或n - 1替換 n 。
返回 n 變為 1 所需的 最小替換次數 。

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

    if(n%2==0)
    return 1+integerReplacement(n/2); 
//1步，n/=2

    return 2+min(integerReplacement(n/2),integerReplacement(n/2+1)); 
//兩步，因為一個奇數+1，-1之後肯定要除以2， 
//n的最大值為2^31-1，若+1，則溢出，所以先對n除以2，再+1，
//floor(n/2)+1 等效於 (n+1)/2    floor(n/2) 等效於 (n-1)/2   floor為向下取整。
    }
};