位運算之尋找數字

原文：https://blog.csdn.net/deaidai/article/details/78167367

位運算基礎

& 按位與

如果兩個相應的二進制位都為1，則該位的結果值為1，否則為0

| 按位或

兩個相應的二進制位中隻要有一個為1，該位的結果值為1

^ 按位異或

若參加運算的兩個二進制位值相同則為0，否則為1 ~ 取反 ~是一進制運算符，用來對一個二進制數按位取反，即将0變1，将1

左移

用來将一個數的各二進制位全部左移N位，右補0

右移

将一個數的各二進制位右移N位，移到右端的低位被舍棄，對于無符号數， 高位補0

原理：

a ^b ^b=a

x&(-x)取x轉換為二進制時的最右的1

問題

數組中，隻有一個數出現一次，剩下都出現兩次，找出出現一次的數。

#include <stdio.h>

int main()

{

int n;

scanf("%d",&n);

int i;

int a[100];

int b=0;

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

b^=a[i];

}

printf("%d",b);

return 0;

}

數組中，隻有兩個數出現一次，剩下都出現兩次，找出出現一次的

#include <stdio.h>
int last(int i)
{
    return i&(-i);
}
int main()
{
    int n;
    scanf("%d",&n);
    int i;
    int a[100];
    int res=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        res^=a[i];
    }
    int l=last(res);
    int b[2]={0};
    for(i=0;i<n;i++)
    {
        if((a[i]&l)==0)b[0]^=a[i];//注意啊a[i]&l要有括号
        else b[1]^=a[i];
    }
    printf("%d %d",b[0],b[1]);
    return 0;
}
           

找出數組中唯一出現一次的數，其它數都出現了三次

一個數從二進制的角度來看，無非就是0和1，若是我們隻從各個位來看，就把這一位的内容加起來，除以3，剩餘的餘數就是單獨剩下的這個數在這一位上的值。

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int i;
    int a[100]={0};
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int b[32]={0};//32位足以儲存資料
    int j;
    int result=0;
    for(i=0;i<32;i++)
    {
        for(j=0;j<n;j++)
        {
            b[i]+=(a[j]>>i)&1;//将每一個a的資料的第j位加到b中，&1時為了将其他位清零
        }
        result |=(b[i]%3)<<i;//将第j位數字複原，|的作用是兩個相應的
    }                        二進制位中隻要有一個為1，該位的結果值為1
   
    printf("%d",result);
    return 0;
}