位操作的奇淫巧技

在计算机中的数在内存中都是以二进制存储的，用位运算就是直接对内存中的二进制进行操作，因此其执行效率很高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。，而在逆向中会出现大量的二进制操作，在分析代码和写脚本方面都有帮助。

下面介绍位运算的操作符都有哪些

位运算操作符

& 与运算 两个位都是 1 时，结果才为 1，否则为 0，如
1 0 0 1 1
& 1 1 0 0 1
------------------------------
1 0 0 0 1

| 或运算 两个位都是 0 时，结果才为 0，否则为 1，如
1 0 0 1 1
| 1 1 0 0 1
------------------------------
1 1 0 1 1

^ 异或运算，两个位相同则为 0，不同则为 1，如
1 0 0 1 1
^ 1 1 0 0 1
-----------------------------
0 1 0 1 0

~ 取反运算，0 则变为 1，1 则变为 0，如
~ 1 0 0 1 1
-----------------------------
0 1 1 0 0

<< 左移运算，向左进行移位操作，高位丢弃，低位补 0，如

int a = 8;
a << 3;
移位前： 0000 1000
移位后： 0100 0000

>> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如

unsigned int a = 8;
a >> 3;
移位前： 0000 1000
移位后： 0000 0001

int a = -8;
a >> 3;
移位前： 1111 1000
移位前： 1111 1111

常见问题解决

实现乘除法

数a 向右移一位，相当于将a除以2；数a向左移一位，相当于乘以2

int a=2;
a >>1 ; -> 1
a <<1;  -> 4

交换数

a ^=b
b^=a
a^=b

判断奇偶数

a&1  ==0 // 偶数

交换符号

int reverse(int a)
{
    return ~a+1;
}

求绝对值

int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}
int abs2(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}

二进制逆序

将无符号数的二进制表示进行逆序，求取逆序后的结果，如

数34520的二进制表示：
10000110 11011000

逆序后则为：
00011011 01100001
它的十进制为7009

在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。

  • 第一步:以每 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);

统计二进制1的个数

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：

  • 第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
  • 第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
  • 第二次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000 我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}

参考链接

位运算的奇技淫巧