位运算与简单应用

一.位运算的基本概念：

首先，位运算是针对二进制的，(数字本来int,4字节,下面假设为1字节)。比如数字12，它的二进制本来是：

0000 0000 0000 0000 0000 0000 0000 1100

因为前面的数字大都是0，所以为了简写，我们保留1字节。在下文中我们12就写成：

0000 1100

二.进制的介绍

进制: 按权展开求和
十进制(0~9):123.45 = 110^2 + 210^1 + 310^0 + 410^-1 + 5*10^-2
二进制(0~1):1010.1 = 2^3+2^1+2^-1=10.5
八进制(0~7):123 = 1*8^2 + 2*8^1+3 = 83
十六进制(0~9,a~f/A~F):123=1*16^2+2*16+3=256+35=291
人(十进制) 计算机(二进制)
人能直接使用二进制吗? 01011010111101101111010110101011,容易看错, 人不能直接使用
二进制能转成十进制吗? 01011010111101101111010110101011,计算量太大：

int main()
{int a = 0x10;//十六进制int b = 20;//十进制int c = 020;//八进制printf("%d,%d,%d\n", a, b, c);//16,20,16printf("%x\n", a);//%x:输出十六进制数字printf("%x\n", 20);//14,printf("%c,%d,%x\n", 65, 65, 65);//'A',65,41printf("%x,%X\n", 20000, 20000);//4e20,4E20//练习//0x124->转二进制->转八进制->转十进制//0x124->0001 0010 0100 -> 444->292return 0;
}

int main()
{int a = 20;int b = 024;//0开头的数据表示八进制数字int c = 0x14;//0x开头的数据表示十六进制int d = 0b10100;//0b开头的数据表示二进制 (新标准增加的)printf("%d,%d,%d,%d\n",a,b,c,d);return 0;
}

三.具体内容

我们以数字12，13举例，

12:0000 1100
13:0000 1101
~12:1111 0011 按位取反
12&13:0000 1100 按位与,相同的位都为1才为1
12 | 13:0000 1101 按位或,相同的位只要有1就为1
12^13:0000 0001 按位异或,相同的位不一样就为1
12<<1:000 11000 按位左移,右边补0(离符号太远) 24=12*2 左移相当于乘法(正数) 乘以2的位移次方
12>>1:00000 110 右移,左边补符号位(如果是无符号数补0,有符号数符号位为0则补0,为1则补 1) 6=12/2 右移相当于除法(正数),除以2的位移次方

四.应用

具体运算如下:下面的运算都是针对二进制

去掉最后一位 | (101101->10110) | x >> 1
在最后加一个0 | (101101->1011010) | x << 1
在最后加一个1 | (101101->1011011) | (x << 1) | 1
把最后一位变成1 | (101100->101101) | x | 1
把最后一位变成0 | (101101->101100) | (x >> 1) << 1 x & ~1
最后一位取反 | (101101->101100) | x ^ 1
把右数第k位变成1 | (101001->101101, k = 3) | x | (1 << (k - 1))
把右数第k位变成0 | (101101->101001, k = 3) | x & 111011->x & ~(1 << (k - 1))
右数第k位取反 | (101001->101101, k = 3) | x ^ 100->x ^ (1 << (k - 1))
1.确定符号 2.确定数字 3.构造数字
得到1 | 1 (这一位是1)
得到0 & 0(这一位是0)
取反 ^ 1
取最右边的1位 | (1101101->1) | x & 1, x % 2
取末三位 | (1101101->101) | x & 111->x & ((1 << 3) - 1), x & 7
取末k位 | (1101101->1101, k = 4) | x & ((1 << k) - 1)
取右数第k位 | (1101101->1, k = 4) | (x >> (k - 1)) & 1

五. 题目

编程1:

所有的数字成对,只有一个数字只出现一次,找到它

//1^3^5^3^1=1^1^3^3^5=5
//找打单的数字
int SingleNum(int* arr, int len)//O(n)
{int tmp = 0;for (int i = 0; i < len; i++)tmp ^= arr[i];return tmp;
}
int main()
{int arr[] = { 1,5,3,7,9,6,1,3,9,6,5 };//所有的数字成对,只有一个数字只出现一次,找//到它//算法1:1.排序;2.遍历 O(nlogn)//算法2:从头到尾按位异或(按位异或相同的数字为0,5^5==0)int n = SingleNum(arr, sizeof(arr) / sizeof(arr[0]));printf("%d\n", n);return 0;
}

编程应用2:

统计一个数字二进制1的个数.例如9转为二进制是0000 1001,那么二进制中1的个数为2.

算法1:利用%2和/2

//统计十进制数字中1的个数例如1231212->3 得个位n%10 ,丢个位n/=10
//统计二进制中1的个数
int Bits(unsigned int n)//-1 ->11111111111111111111111111111111
{int count = 0;//计数器while (n != 0){if (n % 2 == 1)count++;n /= 2;}return count;
}
int main()
{printf("%d\n", Bits(12345678));printf("%d\n", Bits(0x12345678));//1+1+2+1+2+2+3+1printf("%d\n", Bits(-1));//32return 0;
}

算法2:利用位运算,统计最右边1的个数

int Bits2(unsigned int n)
{//n&1:得到二进制右数第1位; n>>=1:丢弃右数第1位int count = 0;while (n != 0)//0x10000000{count += n & 1;n >>= 1;}return count;
}
int main()
{printf("%d\n", Bits(12345678));printf("%d\n", Bits(0x12345678));//1+1+2+1+2+2+3+1printf("%d\n", Bits(-1));//32return 0;
}

算法3:利用x&(x-1)进行统计

int Bits(unsigned int n)
{int count = 0;while (n != 0){count++;n &= n - 1; //丢弃二进制最右边的1}return count;
}
int main()
{printf("%d\n", Bits(12345678));printf("%d\n", Bits(0x12345678));//1+1+2+1+2+2+3+1printf("%d\n", Bits(-1));//32return 0;
}

算法四:

int func(unsigned i) //统计二进制1的个数
{unsigned temp = i;temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa) >> 1);temp = (temp & 0x33333333) + ((temp & 0xcccccccc) >> 2);temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0) >> 4);temp = (temp & 0xff00ff) + ((temp & 0xff00ff00) >> 8);temp = (temp & 0xffff) + ((temp & 0xffff0000) >> 16);return temp;
}
int main()
{printf("%d\n", func(0x7f530829));//3+4+2+2+1+1+2=15return 0;
}