位運算
異或操作也叫半加運算,其運算法則相當于不帶進位的二進制加法;
XOR 在英文裡面的定義為either one (is one), but not both;
異或的主要運用點:任何一個數和自身異或等于0,任何一個數和0異或等于0; 主要運用特性:
異或(^)操作時當且僅當兩個操作數不同時結果為1
與(&)操作時當且僅當兩個操作數都為1時結果為1 (是且是為是)
或(|)操作時隻要有一個操作數為1是結果為1
非(!)操作時就是取反
反(~)操作時按位取反
同或操作時當且僅當兩個操作數相同時結果為1(同或不常用)
算術左移(<
算術右移(>>)時将一個數的各二進制位全部右移若幹位，正數左補0，負數補1(即高位補符号位),右邊舍棄
位運算運用
1. 找出一個二進制數的最右端的第一個1
void findFirstRightOne(unsigned int num){
unsigned int first1R = num & ( (~num)+1 );
printf("%d 的最右端第一個1的十進制數是 %d \n",num,first1R);
}
2. 計算一個二進制數中1的個數
void bit1count(int num){
int cnt = 0;
int tmp = num;
while(tmp!=0){
//先找最後邊第一個1
int right1 = tmp & ( (~tmp)+1 );
++cnt;
//将原數和第一個1異或後,第一個1及其右邊所有的數都将為0
tmp ^= right1;
}
printf("%d 中二進制1的個數為 %d \n", num, cnt);
}
3. 找出數組中唯一一個出現次數為奇數的數
void findOnlyOneOddCountNumber(unsigned int len, int arr[]){
unsigned int i;
int xor = 0;
for(i=0;i
xor = xor ^ arr[i];
}
for(i=0;i
printf("%d ",arr[i]);
}
printf(" 中唯一一個出現次數為奇數次的數是 %d \n",xor);
}
void swapWithNoOtherVar(int *a,int *b){
printf("a:%d, b:%d 交換後為 ",*a,*b);
// 利用了兩個相同的數相異或時等于本身
*a = *a ^ *b;
// a ^ b ^ b = a => 将a的值給了b
*b = *a ^ *b;
// a ^ b ^ a(上一步中b的值已經改為a) = b => 将b的值給了a
*a = *a ^ *b;
printf("a:%d, b:%d \n",*a,*b);
}
4. 找出數組中唯二兩個出現次數為奇數的數
void findOnlyTwoOddCountNumber(unsigned int len, int arr[]){
unsigned int i;
//xor 的結果必然不為0
int xor = 0;
for(i=0;i
xor = xor ^ arr[i];
}
//先找到aor中最右的1 , right1中隻有一位是1,也就是這一位上one和two是不相等的
int right1 = xor & ( (~xor)+1 );
int one = 0;
for(i=0;i
//如果數組中某個數和right1相與不為0,則該數在right1的1的位上的數也為1
//這個操作實際上是将arr分為2組,一組是在right1的1的位上的數也為1,反之為另一組
//因為one和two是不相等的則他們一定在兩個不同的分組
if(arr[i] & right1 != 0){
//這一步配合循環找到該組中唯一一個出現次數為奇數的數
one ^= arr[i];
}
}
//利用 swapWithNoOtherVar 相同的原理得到另外一個數
// xor = one ^ tow ; two = one ^ two ^ one = two
int two = xor ^ one;
for(i=0;i
printf("%d ",arr[i]);
}
printf(" 中唯二兩個出現次數為奇數次的數是 %d , %d \n",one,two);
}
5. 測試
//測試
int main (void){
{
printf("在不消耗額外空間的情況下交換兩個數的值\n");
int a=123,b=321;
swapWithNoOtherVar(&a,&b);
}
//--------------------------
int i;
{
printf("-----找出一個二進制數的最右端的第一個1\n");
for(i=0;i<4;i++){
findFirstRightOne(i);
}
}
//--------------------------
{
printf("-----計算一個二進制數中1的個數\n");
bit1count(123);
}
//--------------------------
{
printf("-----找出數組中唯一一個出現次數為奇數的數\n");
int arr[9];
for(i=1;i<=8;i++){
if(i%2==0) arr[i] = arr[i-1];
else arr[i] = i;
}
arr[0]=111;
findOnlyOneOddCountNumber(9,arr);
}
//--------------------------
{
printf("-----找出數組中唯二兩個出現次數為奇數的數\n");
int arr[10];
for(i=1;i<=8;i++){
if(i%2==0) arr[i] = arr[i-1];
else arr[i] = i;
}
arr[0]=111;arr[9]=112;
findOnlyTwoOddCountNumber(10,arr);
}
return 0;
}
/*
在不消耗額外空間的情況下交換兩個數的值
a:123, b:321 交換後為 a:321, b:123
-----找出一個二進制數的最右端的第一個1
0 的最右端第一個1的十進制數是 0
1 的最右端第一個1的十進制數是 1
2 的最右端第一個1的十進制數是 2
3 的最右端第一個1的十進制數是 1
-----計算一個二進制數中1的個數
123 中二進制1的個數為 6
-----找出數組中唯一一個出現次數為奇數的數
111 1 1 3 3 5 5 7 7 中唯一一個出現次數為奇數次的數是 111
-----找出數組中唯二兩個出現次數為奇數的數
111 1 1 3 3 5 5 7 7 112 中唯二兩個出現次數為奇數次的數是 111 , 112
/*