位运算
异或操作也叫半加运算,其运算法则相当于不带进位的二进制加法;
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
/*