GeorgeYang'Blog

my technology blog

笔记一下二进制在程序中的应用

阅读:277 创建时间:16-03-08 01:49:51 tags:principle,二进制

运算符含义

| 运算符 | 含义 | 功能 | | ------------- |:-------------:| -----:| | & | 按位与 | 如果两个相应的二进制位都为1,则该位的结果值为1;否则为0。| | l| 按位或 | 两个相应的二进制位中只要有一个为1,该位的结果值为1。| | ∧ | 按位异或 | 若参加运算的两个二进制位同号则结果为0(假)异号则结果为1(真)| | ~ | 取反 | ~是一个单目(元)运算符,用来对一个二进制数按位取反,即将0变1,将1变0。| | << | 左移 | 左移运算符是用来将一个数的各二进制位全部左移N位,右补0。| | >> | 右移 | 表示将a的各二进制位右移N位,移到右端的低位被舍弃,对无符号数,高位补0。|

运算符运算

| 运算符 | 或 'l' or| 与 “&”and | 非 “~” not | 异或 “^” xor | | ------------- |:-------------:|:-----:|:-----:|:-----:| | 操作数1| 01010101 |11010101| 10101010 |10000001 |操作数2|00101010|10101010| (无)|01111111| |也能算结果|01111111|10000000|01010101 |11111110

常用二进制数

| 二进制数 | 二进制值| 用处| |-----|:-----:|:-----:| |0xAAAAAAAA |10101010101010101010101010101010|偶数位为1,以1位为单位提取奇位 |0x55555555 |01010101010101010101010101010101|奇数位为1,以1位为单位提取偶位 |0xCCCCCCCC|11001100110011001100110011001100|以“2位”为单位提取奇位 |0x33333333 |00110011001100110011001100110011|以“2位”为单位提取偶位 |0xF0F0F0F0|11110000111100001111000011110000|以“8位”为单位提取奇位 |0x0F0F0F0F |00001111000011110000111100001111|以“8位”为单位提取偶位 |0xFFFF0000|11111111111111110000000000000000|以“16位”为单位提取奇位 |0x0000FFFF |00000000000000001111111111111111|以“16位”为单位提取偶位

运算符的应用:

  • 判断奇偶性:

    bool Parity(Type value)
    {
    if(value & 0x0001 == 0)
    return false;
    else
    return true;
    }
    //加以优化:
    template
    inline bool Parity(Type value)
    {
    return (value & 1 != 0);
    }

  • 是否是2的二次方:

    bool is_pow2(int x) //判断是否2的n次方 { x &= x-1; if(!x) return true; return false; }

    可以写成 return ( (x&(x-1))==0) && (x!=0);

  • 计算绝对值:

    abs( x ) {    y=x>>31 ;    return(x^y)-y;//也可写作 (x+y)^y   }

  • 补码运算公式:

    -x = ~x + 1 = ~(x-1) ~x = -x-1 -(~x) = x+1 ~(-x) = x-1 x+y = x - ~y - 1 = (x|y)+(x&y) x-y = x + ~y + 1 = (x|~y)-(~x&y) x^y = (x|y)-(x&y) x|y = (x&~y)+y x&y = (~x|y)-~x x==y: ~(x-y|y-x) x!=y: x-y|y-x x< y: (x-y)^((x^y)&((x-y)^x)) x<=y: (x|~y)&((x^y)|~(y-x)) x< y: (~x&y)|((~x|y)&(x-y))//无符号x,y比较 x<=y: (~x|y)&((x^y)|~(y-x))//无符号x,y比较

  • 计算平均值:

    int average(int x, int y) //返回X、Y的平均值
    {
    return (x & y) + ( (x^y)>>1 );
    //x&y 取出x和y二进制都为 1 的所有位,这是x、y都为 1 的部分,因为相同,所以直接加就行了
    //x^y x和y中有一个为 1 的所有位
    //后者是x为 1,y为 0的部分,以及y为 1,x为 0 的部分,两部分加起来除以2,然后跟前面的相加就可以了
    }

  • 不用临时变量交换两个数:

    void swap(int x , int y)
    {
    x ^= y;
    y ^= x;
    x ^= y;
    }

    如果x=7,y=8, x^=y>>7^=8,x=15,y=8 y^=x>>8^=15,x=15,y=7 x^=y>> x^=y,x=8,y=7

  • 常用运算(在不产生溢出的情况下):

    取模运算转化成位运算 a % (2^n) 等价于 a & (2^n - 1)

    乘法运算转化成位运算 a * (2^n) 等价于 a<< n

    除法运算转化成位运算 a / (2^n) 等价于 a>> n 例: 12/8 == 12>>3

    a % 2 等价于 a & 1

    if (x == a) x= b; else x= a; 等价于 x= a ^ b ^ x;

  • 统计数字二进制中1的个数: 朴素的统计办法是:先判断n的奇偶性,为奇数时计数器增加1,然后将n右移一位,重复上面步骤,直到移位完毕。

    template
    inline bool Parity(Type value)
    {
    return (value % 2 != 0);
    }

    template
    inline int CountOne(Type value)
    {
    if(value != 0)
    {
    return Parity(value) + CountOne(value >> 1);
    }
    return 0;
    }

另一种统计方法:32位无符 号数的1的个数可以这样数:

 int CountOne(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;  
 }

 再来一种:
 int bitCount(int x) {
   // 把32位划分为8部分,每部分4位。使用掩码0x11111111来获得每部分的最后一位。
   int mask = 0x11 + (0x11 << 8) + (0x11 << 16) + (0x11 << 24);
   // 通过右移、相加,来计数每一部分中1的数量。
   int seg8Count = (x & mask) + ((x >> 1) & mask) + ((x >> 2) & mask) + ((x >> 3) & mask);
   int seg4Count1 = seg8Count + (seg8Count >> 8);
   int seg4Count2 = (seg8Count >> 16) + (seg8Count >> 24);
   // 为了处理相加后的进位问题,我们需要与0x0F进行位与运算,只保留每部分最后4位。
   int result = (seg4Count1 & 0x0F) + ((seg4Count1 >> 4) & 0x0F) + (seg4Count2 & 0x0F) + ((seg4Count2 >> 4) & 0x0F);
   return result;
 }
  • 取非:

    int negate(int x) { return ~x + 1; }

  • 果所有偶数位都是1,则返回1:

    int allEvenBits(int x) { // 把32位划分为4部分,每部分8位。每部分都互相进行位与运算,再和0x55进行位与运算,取偶数位。 // 当且仅当所有偶数位都是1,位与运算的结果才是0x55。然后加上0xAB,将进位变为0x100。 // 如果有偶数位不是1,那么结果必然小于0x55,加上0xAB后,也会小于0x100。 // 因此,这两种情况的区别就在于从右往左数第9位. 右移该位得到最后结果。 int y; int result = 0; y = x & (x >> 16); y = y & (y >> 8); result = ((y & 0x55) + 0xAB) >> 8; return result; }

  • x是否大于y:

    int isGreater(int x, int y) { // 如果x是非负数,y是负数,则flag的标志位为1。在此情况下,x一定大于y。 int flag1 = (~x) & y; // 如果x,y的标志位相同,则flag2的标志位为0。需要进一步比较。 // 如果x,y相等,则flag==0。 int flag2 = x ^ y; // 如果x,y的标志位相同,则不可能发生溢出,除非x,y都是0x80000000。 // 对于x,y都是0x80000000的特殊情况,可以使用x!=y来判断。 // 如果x>y,他们差的标志位将会是0。 int difference = x + (~y + 1); // 只有以下2种情况,result会是1: // 1. flag1是1 (x是非负数,y是负数) // 2. x, y同正负, 并且x-y>=0, 并且x!=y. int result = ((flag1 | ~(flag2 | difference)) >> 31) & 0x01 & !!flag2; return result; }

  • 系统中权限应用:

设各权限值分别如下(2倍等比递增的关系): 1. 列表/查看 = 2 2. 新增 = 4 2. 修改 = 8 4. 删除 = 16

若某个(Role + Module)拥有查看、新增、修改、删除的权限,则其Permission=2+4+8+16=30。 判断Permission是否包含“查看”的权限值,就用 if((Permission & 2) == 2) 判断Permission是否包含“新增”的权限值,就用 if((Permission & 4) == 4) 判断Permission是否包含“修改”的权限值,就用 if((Permission & 8) == 8) 判断Permission是否包含“删除”的权限值,就用 if((Permission & 16) == 16)

  • 图像中颜色应用:

颜色RGB值,我们在这里谈24位颜色。也就是RGB中的R(红)、G(绿)、 B(蓝)分别占8位

 a << 24
     1111 1111 0000 0000 0000 0000 0000 0000
 r << 16
     0000 0000 1111 1111 0000 0000 0000 0000
 g << 8
     0000 0000 0000 0000 1111 1111 0000 0000
 b
     0000 0000 0000 0000 0000 0000 1111 1111

32位颜色除了RGB,还有一个A,即透明度 获取ARGB值:

   var color:uint = 0xff342388;

   var a:uint = color >>> 24 //注意这里是>>>,无符号右移位操作,右移24位,把342388移出,得到0xff
   //也可表示为:((color >> 24) & 255);
   var r:uint = color >> 16 & 0xff;//右移16位,把2388移出,取0x34

   var g:uint = color >> 8 & 0xff;//右移8位,把88移出,得0x3423,与0xff按位与操作,得0x23

   var b:uint = color & 0xff;//得到0x88

生成颜色值:

 public static int ToArgb(this Color color) {
     int argb = color.A << 24;
     argb += color.R << 16;
     argb += color.G << 8;
     argb += color.B;
     return argb;
 }
  • 游戏中角色状态应用:

假设游戏状态如下:

 enum EPLAYER_STATE
     {
         EPST_NONE    = 0x00000000,     // 没有状态
         EPST_ADDHP  = 0x00000001 ,    // 加血
         EPST_ADDMP  = 0x00000002,     // 加蓝
         EPST_ADDSP   = 0x00000004,    // 加体力
         EPST_JMDAM   = 0x00000008,    // 经脉受伤
         EPST_DIANX    = 0x00000010,    // 被点穴
         EPST_XUANY    = 0x00000020,    // 被眩晕
         EPST_ATTCK    = 0x00000040,    // 被攻击
         // ... ...
         // 最多可以写32个状态,已经足够了。为什么是32,因为一个32位整数来存放的。
     };

初始状态:

 UINT dwPlayerState = EPST_NONE;

判断它是否存在某种状态

   if ( dwPlayerState &  EPST_ADDMP )  // 判断是否这位上是否为1
     {
             // 不能再吃蓝药啦。。
     }

假如我要同时加上几个状态的话。那么:

 dwPlayerState |= ( EPST_ADDMP| EPST_ADDSP| EPST_JMDAM );

如果我要清掉状态:

 // 清除蓝药状态
 dwPlayerState &= ~EPST_ADDMP;   // 这样便清掉了。
 // 清除多个状态
  dwPlayerState &= ~( EPST_ADDMP| EPST_ADDSP| EPST_JMDAM );

参考,参考,参考,参考,参考,参考,参考,参考,参考,参考,参考,参考