遇見藍橋遇見你，不負代碼不負卿！
目錄
目錄
一、位運算子總結概述
1、按位與 &
2、按位或 |
3、按位取反 ~
4、按位異或 ^
5、補充了解移位運算
1.左移<<
2.右移>>
3.無符號右移>>>
6、補充了解原碼反碼補碼
1.原碼
2.反碼
3.補碼
二、藍橋云課：位運算的奇巧淫技
1、判斷奇偶數
?
解題思路：
代碼執行
2、判斷二進制位是1還是0（兩種方法）
方法一解題思路
代碼執行
方法二解題思路
代碼執行
3、交換兩個整型變數的值（異或法）
解題思路
代碼執行
4、不用判斷陳述句，求整數的絕對值
解題思路
代碼執行
三、實戰例題
例1、如何找陣列中唯一成對的那個數
解題思路
代碼執行
例2、找出落單的那個數
解題思路
代碼執行
例3、二進制中1的個數
方法1解題思路
代碼執行
方法2解題思路
代碼執行
方法3解題思路
代碼執行
例4、是不是2的整數次方
解題思路
代碼執行
例5、將整數的奇偶位互換
解題思路
思考題：出現K次與出現一次
四、藍橋結語：遇見藍橋遇見你，不負代碼不負卿！
五、筆者請求
【前言】：筆者是根據藍橋杯官方發布的視頻整理出的筆記，博文是由筆記二次整理而來，具有較強的針對性，打算參賽的小伙伴跟著筆者一起行動起來吧！為了方便更多的鐵汁們，代碼示例中筆者采用的是C語言撰寫，
【友情提示】：在接下來的兩個半月中，博主將會持續推出兩個系列的博文，一是零基礎搞定C語言，二是藍橋杯演算法競賽，包括一些刷題感悟與總結哦，當然后面還會有往年的藍橋杯真題總結，喜歡的鐵汁們可以關注筆者哦，
一、位運算子總結概述
1、按位與 &
如果兩個二進制位都為1，則結果是1，否則是0
2、按位或 |
如果兩個二進制位都為0，則結果是0，否則是1
3、按位取反 ~
該位為0，則變為1，否則變為0
4、按位異或 ^
如果兩個數字的二進制位相同，則結果為0，相異則結果為1
5、補充了解移位運算
實際運用當中可以根據情況用左移/右移做快速的乘除法，這樣效率會高很多，
1.左移<<
最左側不要了，最右側直接補0；（左移相當于乘法，如左移1位，相當于乘以2的1次方）
2.右移>>
右移相當于除法...
因為C語言中沒有特別引入無符號右移，所以C語言中的右移分成算術右移和邏輯右移兩種，
算術右移就是最右側位不要了，最左側直接補符號位（大多數機器上采用的是算術右移）
所以應用C語言中的右移需要格外注意負數的情況，
邏輯右移就是最右側不要了，最左側直接補0
注意：對于int 型別的資料，移位超出32位時，需要模上32，比如1 << 35 == 1 << 3；
那么對于long型別來說，超出時需要模上64（模-->求余）
3.無符號右移>>>
引入Java中的無符號右移，它和左移的用法一直，也就是邏輯右移，最右側不要了，最左側補0
6、補充了解原碼反碼補碼
1.原碼
直接將這個數字按照正負數的形式翻譯成二進制即可
2.反碼
原碼的符號位不變，其他位按位取反即可
3.補碼
反碼+1即可得到補碼
注意：正數和無符號數的原碼、反碼、補碼都相同，只有求負數的反碼、補碼才采用上面的計算
int a = 20; //整型a是4個位元組，32位
// 00000000 00000000 00000000 00010100 - 原碼
// 00000000 00000000 00000000 00010100 - 反碼
// 00000000 00000000 00000000 00010100 - 補碼
int b = -10;
// 10000000 00000000 00000000 00001010 - 原碼
// 11111111 11111111 11111111 11110101 - 反碼
// 11111111 11111111 11111111 11110110 - 補碼宣告：對于資料的存盤只簡單介紹到這里，詳細介紹將放在后面零基礎搞定C語言系列
二、藍橋云課：位運算的奇巧淫技
1、判斷奇偶數
解題思路：
拿int型舉例，int占4個位元組，也就是32位，對于整型來說，資料存放在記憶體當中存放的是其補碼形式，由于第一位(注意上面圖片中第1位的位置)前面的數都是2的1及以上次方，只有當第一位是1時為奇數，是0時為偶數，大家先理解一下上面這句話，明白了以后，如果我們想要判斷一個整數的奇偶性，只需要和1進行按位&運算即可，由于1中除第1位以外每一位都是0，又因為任何數中的每一位與1中的0位做&運算，與0位做&運算的位結果都是0，所以偶數和1進行&運算是0，奇數和1進行&運算是1
代碼執行
#include<stdio.h>
int main()
{
printf("判斷奇偶數：\n");
int num = 12;
if ((num & 1) == 0)
{
printf("%d是偶數\n",num);
}
else
{
printf("%d是奇數\n", num);
}
return 0;
}2、判斷二進制位是1還是0（兩種方法）
例：int x = 86; // 定義一個整型變數x, 并將其初始化為86
現需要判斷第5位是1還是0， 該如何操作？
方法一解題思路
老樣子，還是用整數1執行操作，由于是判斷x的第五位是1還是0，所以取整數1，讓1左移（5 - 1）位，也就是左移4位，然后直接和x進行按位&操作，最后再右移4位至該數二進制第一位，若第1位是0，則第5位上的二進制數是0，否則是1
代碼執行
#include<stdio.h>
int main()
{
int x = 86;
printf("判斷整數86的二進制第5位是1還是0:\n");
//運算子的使用有優先級，我們不必特意去記這個，可能存在歧義的時候，就加上括號，這樣既保險又省心
if ((((1 << 4) & x) >> 4) == 0)
{
putchar('0');
}
else
{
putchar('1');
}
return 0;
}方法二解題思路
該方法較方法一就簡單多了，它利用了“判斷奇偶數”的解題思想，首先，讓x右移（5 - 1）位，即右移4位，然后再和1相&，如果結果是0，則第5位上的二進制數是0，否則是1，
代碼執行
#include<stdio.h>
int main()
{
int x = 86;
printf("判斷整數86的二進制第5位是1還是0:\n");
if (((x >> 4) & 1) == 0)
{
putchar('0');
}
else
{
putchar('1');
}
return 0;
}3、交換兩個整型變數的值（異或法）
解題思路
補充：異或，可理解為不進位加法，如1+1 = 0, 0 + 0 = 0, 1 + 0 = 1
異或：如果兩個數字的二進制位相同，則結果為0，相異則結果為1.
異或的性質：
1.交換律：可任意交換運算因子的位置，結果不變；
如：a ^ b ^ c = b ^ a ^ c;
2.結合律：即(a ^ b) ^ c == a ^ ( b ^ c) ;
3.對于任何數x, 都有x ^ x = 0, x ^ 0 = x,同自己求異或為0，同0求異或為自己
4.自反性：A ^ B ^ B = A ^ 0 = A, 連續和同一個因子做異或運算，最終結果為自己
說了這么多，那么位運算中的異或到底跟“交換兩個整型變數的值”這個題目有什么聯系呢，請聽筆者向鐵汁們慢慢道來...
例題：int A = 10, int B = 20, 在不引入第3個變數的情況下，交換兩個變數的值（除了采用異或法，用加減法也可以，這個將在后面的零基礎搞定C語言中詳細介紹）
代碼執行
#include<stdio.h>
int main()
{
int A = 10;
int B = 20;
printf("交換前A = %d B = %d\n", A, B);
A = A ^ B;
B = A ^ B;
A = A ^ B;
printf("交換后A = %d B = %d\n", A, B);
return 0;
}4、不用判斷陳述句，求整數的絕對值
解題思路
如果上面的表述看不懂也沒有關系，運算式已經給出來了，你只需要知道當遇到不用判斷陳述句求整數的絕對值用它即可，
代碼執行
本題采用Java語言撰寫
public class Test10_16 {
public static void main(String[] args) {
System.out.println("不用判斷陳述句，求整數的絕對值");
int num5 = -100;
System.out.println("num5的絕對值是：" + ((num5 ^ (num5 >> 31)) + (num5 >>> 31)));
}
}三、實戰例題
例1、如何找陣列中唯一成對的那個數
1-10這10個數放在含有11個元素的陣列中，只有唯一一個元素重復，其他均只出現一次，要求每個陣列元素只能夠被訪問一次，請設計一個演算法，將它找出來，不用輔助存盤空間，能否設計一個演算法實作？
解題思路
想要計算出本題，需要我們掌握異或的性質，思路：定義一個數x，并將它初始化成0，將它和陣列中的11個數異或，再和1-10這10個自然數異或，最終的結果就是那個數，
代碼執行
#include<stdio.h>
int main()
{
int arr[] = { 1,2,3,2,6,4,7,5,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
int x = 0;//之所以將x初始化為0，因為0與任何數異或都是它自己
for (int i = 0; i < sz; i++)
{
x = x ^ arr[i];
}
for (int i = 1; i <= sz - 1; i++)
{
x = x ^ i;
}
printf("%d\n", x);
return 0;
}例2、找出落單的那個數
一個陣列中除了某一個元素中之外，其他的元素都出現了兩次，請寫程式找出這份只出現一次的數字
解題思路
這道題比第一道題還要簡單，直接異或即可
代碼執行
#include<stdio.h>
int main()
{
int arr[] = { 1,1,2,3,3,4,4,5,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
int x = 0;
for (int i = 0; i < sz; i++)
{
x = x ^ arr[i];
}
printf("%d\n", x);
return 0;
}例3、二進制中1的個數
輸入一個整數，輸出該數二進制表示中1的個數
如9的二進制表示為00000000 00000000 00000000 00001001，有兩個1
方法1解題思路
笨方法，把1給數出來-->讓1動，那個整數一直不動，利用32次回圈，每一次都是將相應位上的數字進行按位&操作
代碼執行
#include<stdio.h>
int main()
{
int num = 9;
int count = 0;//用于計數
for (int i = 0; i < 32; i++)
{
//一定要注意寫法，雖然簡單，但是容易出錯
if ((num & (1 << i)) == (1 << i))-----注意寫成if((num & (1 << i) == 1)就錯了
{
count++;
}
}
printf("%d\n", count);
return 0;
}方法2解題思路
其實就是方法1的一個變形，保持1的位置不動，讓那個整數不斷右移
代碼執行
#include<stdio.h>
int main()
{
int num = 9;
int count = 0;
for (int i = 0; i < 32; i++)
{
if (((num >> i) & 1) == 1)
{
count++;
}
}
printf("%d\n", count);
return 0;
}
方法3解題思路
技多不壓身，鐵汁們最好將這三種方法全部掌握，保不準在之后的題目中會用到，
利用回圈，當這個整數變為0時回圈結束，回圈體中執行num = (num - 1) & num 這個操作
可能大家一開始的時候想不到這個解法，筆者也是，我一開始看的時候也很蒙，但是當你看完了之后會有種醍醐灌頂的感覺，說明你理解了原來還可以這樣，雖然之前我們可能想不到，但是既然現在遇到了，那就要記住它，以后再出現的時候就要會運用了，一起加油吧鐵汁們，
代碼執行
#include<stdio.h>
int main()
{
int num = 9;
int count = 0;
while (num != 0)
{
num = (num - 1) & num;
count++;
}
printf("%d\n", count);
return 0;
}例4、是不是2的整數次方
同一條陳述句判斷一個整數是不是2的整數次方
解題思路
判斷一個整數是不是2的整數次方，也就是這個整數的二進制中只有一個1
代碼執行
看，這里就用到了上一題的方法3，所以我們該不該記住呢...
#include<stdio.h>
int main()
{
int num = 9;
if (((num - 1) & num) == 0)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}例5、將整數的奇偶位互換
注意：用1做&運算其實就是保留，用0做&運算其實就是消除
解題思路
#include<stdio.h>
int main()
{
int num = 9; //0000....00001001
int a = 0xaaaaaaaa; //1010....10101010
int b = 0x55555555; //0101....01010101
int c = num & a; //目的是保留num的偶數位
int d = num & b; //目的是保留num的奇數位
printf("%d\n", ((c >> 1) ^ (d << 1)));
return 0;
}
思考題：出現K次與出現一次
題目描述：陣列中只有一個數出現了1次，其他數都出現了K次，請輸出這出現一次的數，需要用位運算，不可以采用暴力求解法，
注意：以后筆者的博文中可能每篇都會有下一道思考題留給鐵汁們做，等到筆者下次發表該系列博文的時候會公布解題思路和代碼執行，權當復習了，
四、藍橋結語：遇見藍橋遇見你，不負代碼不負卿！
大學可以說是人生中最美好的階段，我們雖然有壓力，但是相比以后作業、生活而言就算不上什么了，對于身處IT浪潮中的我們而言，愿大家不負韶華，珍惜機會，豐富經歷，學有所成，
五、筆者請求
鐵汁們，筆者的博文都是由紙質和電子筆記的二次加工而來的，花費了比較多的心力，感覺寫的還可以的話，給俺來個點贊，收藏加關注唄，你們的支持就是筆者最大的動力
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/323447.html
標籤：其他