二进制运算技巧

二进制运算常用技巧

1、 用于整数的奇偶性判断

一个整数a, a & 1 这个表达式可以用来判断a的奇偶性。二进制的末位为0表示偶数,最末位为1表示奇数。若a为奇数,则a & 1 的结果等于1。

2、 判断n是否是2的正整数冪

(!(n&(n-1)) ) && n

好!看完上面的两个小例子,相信大家都有一个感性的认识。从理论上讲,如果一个数a他是2的正整数幂,那么a 的二进制形式必定为1000……(后面有0个或者多个0),那么结论就很显然了。

3、 统计n中1的个数

朴素的统计办法是:先判断n的奇偶性,为奇数时计数器增加1,然后将n右移一位,重复上面步骤,直到移位完毕。
朴素的统计办法是比较简单的,那么我们来看看比较高级的办法。

举例说明,考虑2位整数 n=11,里边有2个1,先提取里边的偶数位10,奇数位01,把偶数位右移1位,然后与奇数位相加,因为每对奇偶位相加的和不会超过“两位”,所以结果中每两位保存着数n中1的个数;相应的如果n是四位整数 n=0111,先以“一位”为单位做奇偶位提取,然后偶数位移位(右移1位),相加;再以“两位”为单位做奇偶提取,偶数位移位(这时就需要移2位),相加,因为此时没对奇偶位的和不会超过“四位”,所以结果中保存着n中1的个数,依次类推可以得出更多位n的算法。整个思想类似分治法。
在这里就顺便说一下常用的二进制数:
0xAAAAAAAA=10101010101010101010101010101010
0x55555555 = 1010101010101010101010101010101(奇数位为1,以1位为单位提取奇偶位)
0xCCCCCCCC = 11001100110011001100110011001100
0x33333333 = 110011001100110011001100110011(以“2位”为单位提取奇偶位)
0xF0F0F0F0 = 11110000111100001111000011110000
0x0F0F0F0F = 1111000011110000111100001111(以“8位”为单位提取奇偶位)
0xFFFF0000 =11111111111111110000000000000000
0x0000FFFF = 1111111111111111(以“16位”为单位提取奇偶位)
例如:32位无符号数的1的个数可以这样数:
int count_one(unsigned long n)
{
//0xAAAAAAAA,0x55555555分别是以“1位”为单位提取奇偶位
n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);
//0xCCCCCCCC,0x33333333分别是以“2位”为单位提取奇偶位
n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);

//0xF0F0F0F0,0x0F0F0F0F分别是以“4位”为单位提取奇偶位
n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);

//0xFF00FF00,0x00FF00FF分别是以“8位”为单位提取奇偶位
n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF);

//0xFFFF0000,0x0000FFFF分别是以“16位”为单位提取奇偶位
n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF);

return n;

}
举个例子吧,比如说我的生日是农历2月11,就用211吧,转成二进制:
n = 11010011
计算n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);
得到 n = 10010010
计算n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);
得到 n = 00110010
计算n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);
得到 n = 00000101 —————–à无法再分了,那么5就是答案了。
4、对于正整数的模运算(注意,负数不能这么算)
先说下比较简单的:
乘除法是很消耗时间的,只要对数左移一位就是乘以2,右移一位就是除以2,传说用位运算效率提高了60%。
5.左移右移:
左移乘2,右移除以2,都是整除。5的二进制表示是101那么右移一位之后是10就是2了,是整除的,把最后一位拿掉了。左移的话就是在后面补一个零,相当于是乘以二,那么变成了1010,十进制是10
e = e >> 1 #e右移一位,相当于除以2,与while(e>0)连用,可计算开二次方的次数,因为移到最后一位变成0

    原文作者:chengfree
    原文地址: https://blog.csdn.net/chengfree/article/details/94718917
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞