位操作技巧
2019-09-16 本文已影响0人
盼旺
位操作符
& 与运算 两个位都是 1 时，结果才为 1，否则为 0
| 或运算 两个位都是 0 时，结果才为 0，否则为 1
^ 异或运算，两个位相同则为 0，不同则为 1
~ 取反运算，0 则变为 1，1 则变为 0
<< 左移运算，向左进行移位操作，高位丢弃，低位补 0
>> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位
unsigned int a = 8;
a >> 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
移位前：1111 1111 1111 1111 1111 1111 1111 1000
移位前：1111 1111 1111 1111 1111 1111 1111 1111
实现技巧
消去二进制最后一个1 ,a &= (a-1)
取右边第一个1所在位置 x&-x
如果要获得第 i 位的数据，判断((data&(1<<i)) == 0)，若真，为 0，假，为 1；
如果要设置第 i 位为 1，data = (data|(1<<i))；
如果要设置第 i 位为 0，data = (data&(~(1<<i)))；
如果要将第 i 位取反，data = (data^(1<<i)；
如果要取出一个数的最后一个 1 (lowbit),(data&(-data))；
取末k位， x & ((1 < < k)-1) (1101101->1101,k=5)
将正数变成负数，负数变成正数,return ~a + 1;
把右边连续的1变成0，x & (x+1) (100101111->100100000)
把右起第一个0变成1， x | (x+1) (100101111->100111111)
把右边连续的0变成1 ，x | (x-1) (11011000->11011111)
取右边连续的1 ，(x ^ (x+1)) >> 1 (100101111->1111)
去掉右起第一个1的左边， x & (x ^ (x-1)) (100101000->1000)
无符号数的二进制表示进行逆序 见下例子1
输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n 见下例子2
将一个十进制的数分解为二进制表示. 见下例子3
算一个数二进制的补位数(比如说5的二进制是101, 所以补位数就是010, 即2,当然不能直接用~)见下例子4
(1)整数的平均值对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，
但是我们知道它们的平均值是肯定不会溢出的，我们用如下
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
/*大概思路应该是这样：
(x&y)+((x^y)>>1)，把x和y里对应的每一位（指二进制位）都分成三类，每一类分别计算平均值，最后汇总。
其中，一类是x,y对应位都是1，用x&y计算其平均值；
一类是x,y中对应位有且只有一位是1，用(x^y)>>1计算其平均值；
还有一另是x,y中对应位均为0，无须计算。
说明一下前两种情况是怎样计算的：
x,y对应位均为1，相加后再除以2还是原来的数，如两个00001111相加后除以2仍得00001111，这是第一部分。
第二部分，对应位有且只有一位为1，用“异或”运算提取出来，然后>>1(右移一位，相当于除以2），即到到第二部分的平均值。
第三部分，对应位均为零，因为相加后再除以二还是0，所以不用计算。
三部分汇总之后就是(x&y)+((x^y)>>1)
*/
(2) x 的 相反数 表示为 (~x+1)
例子1
数34520的二进制表示：
10000110 11011000
逆序后则为：
00011011 01100001
它的十进制为7009
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。
第一步:以每 2 位为一组
组内进行高低位交换交换前：10 00 01 10 11 01 10 00
交换后： 01 00 10 01 11 10 01 00
第二步：在上面的基础上，以每 4 位为 1 组
组内高低位进行交换交换前： 0100 1001 1110 0100
交换后： 0001 0110 1011 0001
第三步：以每 8 位为一组
组内高低位进行交换交换前： 00010110 10110001
交换后： 01100001 00011011
第四步：以每16位为一组
组内高低位进行交换交换前： 0110000100011011
交换后： 0001101101100001
对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐，下面介绍另外一种方法进行处理。
这里先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：
原数： 10000110 11011000
奇数位： 10000010 10001000
偶数位： 00000100 01010000
再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可以达到奇偶位上数据交换的效果：
原数： 10000110 11011000
奇数位右移一位： 0 10000010 1000100
偶数位左移一位：0000100 01010000 0
两数相或得到： 01001001 11100100
上面的方法用位操作可以表示为：
取a的奇数位并用 0 进行填充可以表示为：a & 0xAAAA
取a的偶数为并用 0 进行填充可以表示为：a & 0x5555
因此，上面的第一步可以表示为：
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理，可以得到其第二、三和四步为：
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整个操作为：
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
例子2
思路: 结合异或的性质运算,首先让 m^n 得到一个数,则这个数二进制中有多少个1 , 则m,n就有多少位不同.所以统计得到的这个数中又多少个1就行了.
int check(int m,int n)
{
int x=m^n;
int num=0;
while(x)
{
x &= (x-1);
num++;
}
return num;
}
例子3
while(t){
int m=t&1;
a[k++]=m;
t >>= 1;
}
例子4
int sum=0,s=1;
while(t){
int m=((t&1)^1);//现得到这位是0还是1 然后异或取反
sum += s*m; //是1才算值, 是零就不管.
t >>= 1; //不断除二.
s <<= 1; //s表示2的几次方.
}
