C語言 位運算運算子及應用（騷操作）

C語言長盛不衰霸榜長久的一部分原因，在于它對于計算機底層的操作，位運算，作為實作底層操作的一部分功能值得我們關注，
當然從功利的角度而言，位運算在以后的面試、筆試程序中對我們有著極大的便利，

前言：
首先需要了解整數儲存的機制；
原碼、反碼、補碼；
三種碼都是32位的二進制數
輸出靠原碼，記憶體存補碼；
1、正整數原碼、反碼、補碼相同，直接進行二進制轉換就可；（2^32-1個正整數）
2、負整數32位的首位為符號位（1代表負數）；（2^31-1個符數）
原碼將剩余的31位通過負整數的絕對值進行二進制轉化
反碼是符號位不變，其余位數取反
補碼是反碼+1
3、0是一個特殊的數，由于符號位存在，分為+0，-0；
+0 為00000000000000000000000000000000
-0 為10000000000000000000000000000000

Part 1:位運算運算子
（1）& 按位與 ：如果兩個相應的二進制位都為1，則該位結果為1，否則為0，

#include<stdio.h>
int main(){
    int a = 15;   //00000000000000000000000000001111
    int b = 19;   //00000000000000000000000000010011
    int c = a & b;//00000000000000000000000000000011
    printf("%d", c);//輸出結果為3
    return 0;
}

（2）| 按位或：兩個對應的二進制位只要有一個為1，則該位結果為1，否則為0；

int main(){
    int a = 15;   //00000000000000000000000000001111
    int b = 19;   //00000000000000000000000000010011
    int c = a | b;//00000000000000000000000000011111
    printf("%d", c);//輸出結果為31
    return 0;
}

（3）^按位異或：兩個對應的二進制位不同時則該位結果為1，否則為0；

int main(){
    int a = 15;   //00000000000000000000000000001111
    int b = 19;   //00000000000000000000000000010011
    int c = a ^ b;//00000000000000000000000000011100
    printf("%d", c);//輸出結果為28
    return 0;
}

（4）~取反：對該數的二進制位，若該位為1則結果為0，若改為為0則結果為1；

int main(){
    int a = 19;//00000000000000000000000000010011
    int b = ~a;//11111111111111111111111111101100(記憶體中的補碼)
               //11111111111111111111111111101011（反碼，即補碼-1）
               //10000000000000000000000000010100（原碼，即反碼符號位不變，其余位數取反）
    printf("%d", b);//輸出結果-28
    return 0;
}

（5）<<左移運算子：將一個數的各二進制位向左平移i個單位(<<為雙目運算子，通常寫為a<<i），高位溢位的刪去，地位補0；

int main(){
    int a = 19;  //00000000000000000000000000010011
    int b = a<<1;//00000000000000000000000000100110
    printf("%d", b);//輸出結果38
    return 0;
}

（6）>>右移運算子；將一個數的各二進制位向右平移i個單位（用法同左移運算子），根據編譯器不同分為兩種不同的右移
1、邏輯右移：右邊溢位位數丟棄，左邊高位補0
2、算術右移：右邊溢位位數丟棄，左邊根據符號位補位

int main(){
    int a = -19; //10000000000000000000000000010011（原碼）
                 //11111111111111111111111111101100（反碼）
                 //11111111111111111111111111101101(補碼)
    int b = a>>1;//11111111111111111111111111110110（補碼）
                 //11111111111111111111111111110101（反碼）
                 //10000000000000000000000000001010（原碼
    printf("%d", b);//輸出結果-10
    return 0;
}

Part 2 一些重要的注意點：
1、所有的位運算子，均只能對整型使用；
2、位運算子操作的都是該數儲存在記憶體中的補碼，而printf輸出的都是原碼，所以針對負整數，我們需要先轉化成補碼，進行操作后，再轉換成原碼輸出，
3、>> <<中移的位數i 為正整數，使用負整數為UB（Undefined Behavior）

Part3 位運算運算子的一些應用：
1、scanf函式輸入錯位回傳值為-1
而~-1==0 利用這一特性我們可以實作回圈多行輸入

int a=0;
while(~scanf("%d",&a)){
;
}

2、除號，乘號可以利用>>,<<代替；
事實上，c語言編譯器在運行的時候會將你的/2優化為>>1，將你的*2優化為<<1，利用位運算子其實可以優化程式運行速度；從另一個角度，在筆試面試中將簡單的乘除法替換成位運算子，能顯示出更高水平（霧

#include<math.h>
int main(){
    int a = 120;
    int i = 0;
    int temp = 1;
    for (i = 1; i <= 3;i++){
        temp *= 2;
        printf("%d\n", a >> i);//右移相當于?（2^i）,左移相當于×（2^i）
        printf("%d\n", a / temp);
    }
    return 0;
}

3、交換兩個變數的值，且同時不創造新的臨時變數；

int main(){
    int a = 10, b = 5;
    printf("a=%d b=%d\n", a, b);
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("a=%d b=%d", a, b);
    return 0;
}

4、判斷整型數二進制轉化后1的個數
（可以結合應用2理解）

int main(){
    int a = 55,count=0;//55-->00000000000000000000000000110111
                       //1 -->00000000000000000000000000000001
                       //a&1->00000000000000000000000000000001
                       //a/2->00000000000000000000000000011011
    while(a>0){
        if(a&1==1){
            count++;
        }
        a = a / 2;
    }
    printf("%d", count);
}

5、關于n&（n-1)的一些騷應用
（1）判斷一個數是否為2的次方項，首先我們觀察到2的二進制表示為10，4為100，8為1000…以此類推，2的次方項的二進制表達有一定的規律
2的二進制10-------1的二進制 01----- 2&1得 0
4的二進制100-----3的二進制011-----4&3得 0
8的二進制1000----7的二進制0111—8&7得 0
于是我們發現n&(n-1)==0的時候n為2的次方項，背后的原理其實很簡單，類似十進制的退位原理，2的次方項轉化成二進制，就類似于十進制中的10的n次方，此時-1后，它的各位一定與原來的數均不相同，

int is_two_pow(int n){
    if((n&(n-1))==0){
        return 1;
    }else{
        return 0;
    }
}

（2）統計一個數的二進制轉化后有多少個1（同上文4）
程序類比于判斷2的次方，對轉化后的每一個1進行類似于上文的比較，count每一次加一后的n=n&（n-1）都會使得n二進制內的一個1消失

int count_one(int n){
    int count = 0;
    while(n>0){
        count++;
        n = n & (n - 1);
    }
    return count;
}
int main(){
    int a = 55;//55-->   00000000000000000000000000110111
               //54-->   00000000000000000000000000110110
               //55&54-->00000000000000000000000000110110-->54
               //53-->   00000000000000000000000000110101
               //54&53-->00000000000000000000000000110100-->52
               //51-->   00000000000000000000000000110011
               //52&51-->00000000000000000000000000110000--48
               //47-->   00000000000000000000000000101111
               //47&46-->00000000000000000000000000100000--32
               //31-->   00000000000000000000000000011111
               //32&31-->00000000000000000000000000000000--0 回圈結束
    printf("%d", count_one(a));
    return 0;
}

總結：n&（n-1）非常巧妙的利用了二進制的運算規律，其實本質并不復雜，難點只是在于，長時間進行了十進制運算后，大腦短暫難以迅速理解二進制，n=n&（n-1）的本質是將n二進制轉化后的最后一個1變成0
6、實作轉化后二進制的逆序

int reverse(int n){
    int result = 0;
    for (int i = 0; i < 32;i++){
        result = result << 1;//左移1位留出空格
        result += (n&1);//n&1得出n二進制的最后一位
        n >>1;//n右移一位獲得下一位
    }
    return result;
}

7、實作正負數轉化
正數取反+1得到負數得補碼，-1后再取反（此時符號位不變）得到負數的原碼
負數補碼取反+1，得到符號位變為0的其原碼

int pos_neg(int n){
     return ~n+1;
}

8、實作取絕對值操作

int my_abs(int n){
   int i=n>>31;//獲取符號位
   return i==0? n:~n+1;
}

Part 4 總結：
以上只是一些淺層次的理解，挖坑日后繼續補充，
位運算操作，更符合c語言編譯器的需求，畢竟計算機的本質是二進制運算，可以優化程式效率，當然在另一層面，更體現了撰寫者對語言的理解，從而在面試、筆試中留下更好的印象，