位运算

异或操作也叫半加运算,其运算法则相当于不带进位的二进制加法;

XOR 在英文里面的定义为either one (is one), but not both;

异或的主要运用点:任何一个数和自身异或等于0,任何一个数和0异或等于0; 主要运用特性:

异或(^)操作时当且仅当两个操作数不同时结果为1

与(&)操作时当且仅当两个操作数都为1时结果为1 (是且是为是)

或(|)操作时只要有一个操作数为1是结果为1

非(!)操作时就是取反

反(~)操作时按位取反

同或操作时当且仅当两个操作数相同时结果为1(同或不常用)

算术左移(<

算术右移(>>)时将一个数的各二进制位全部右移若干位，正数左补0，负数补1(即高位补符号位),右边舍弃

位运算运用

1. 找出一个二进制数的最右端的第一个1

/**找出一个二进制数的最右端的第一个1*/

void findFirstRightOne(unsigned int num){

/*一个数取反+1

* 如00101011000 取反

* 为11010100111 加1

* 为11010101000 则其与原数相比

* 其第一个1右边的所有数都为0,左边的数都相等

* 此时将他们相与,则只有第一个1的位置的结果为1

* (0与任何数值为0,仅当1与1时为1)

*/

unsigned int first1R = num & ( (~num)+1 );

printf("%d 的最右端第一个1的十进制数是 %d \n",num,first1R);

}

2. 计算一个二进制数中1的个数

/**计算一个二进制数中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;

/*任何一个数和自身异或等于0,任何一个数和0异或等于0

* 异或操作也叫半加运算,其运算法则相当于不带进位的二进制加法

* XOR 在英文里面的定义为either one (is one), but not both

*/

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

/*