原理剖析 常见位运算技巧

阅读量

关于位运算的优越之处，无论用在嵌入式开发或者系统核心代码的调优上，有大把的文章去介绍其迷人的特性；在日常程序里面适当添加一些位运算的逻辑也会让你的代码增色不少；当然如果在普通程序中大量使用，在可读性上就是一种糟糕的体验了。这里就一些常用的位运算技巧进行解析，也方便对这些技巧进行记忆！

『首先』 使用位运算前，切记注意场景，并进行严格测试，我们这里使用一个常用的 ‘交换数值运算’ 进行对比测试：

1
[wettper@web-lovers ctest]$ vim bit_operation.c

中间变量交换（循环运算 10000000 耗时 0m0.029s）：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main ()
{
    int c, i = 0, a = 1, b = 2;
    while (i <= 10000000) {
        i ++;
        c = a;
        a = b;
        b = c;
    }
    printf("a: %d, b: %d \n", a, b);
    return 0;
}

1
2
3
4
5
6
[wettper@web-lovers ctest]$ gcc bit_operation.c -g -o bit_operation && time ./bit_operation
a: 2, b: 1
real    0m0.029s
user    0m0.028s
sys 0m0.000s

异或运算交换（循环运算 10000000 耗时 0m0.068s）：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main ()
{
    int c, i = 0, a = 1, b = 2;
    while (i <= 10000000) {
        i ++;
        a ^= b;
        b ^= a;
        a ^= b;
    }
    printf("a: %d, b: %d \n", a, b);
    return 0;
}

1
2
3
4
5
6
[wettper@web-lovers ctest]$ gcc bit_operation.c -g -o bit_operation && time ./bit_operation
a: 2, b: 1
real    0m0.068s
user    0m0.067s
sys 0m0.000s

所以：

  • 并不是所有位运算逻辑一定是更快或者更高效的。
  • 不同平台上的效果可能不太一致。

『但是』 不可否认位运算的优越性，还是很值得我们学一下，我们针对常用的技能进行解释，同时也重温一下位运算的语法

获得int型最大值

1
2
3
4
5
// @return 2147483647
int get_max_int()
{
    return (1 << 31) - 1;
}

<< 左移操作 A << B 将 A 的二进制表示的整体向左移 B 位，左边超出 32 位的截掉（如果是 int 的话），右边不足的位补 0。[标注1]

1
2
1 << 31 = 10000000000000000000000000000000
(1 << 31) - 1 = 1111111111111111111111111111111 (31位, int所能达到的最大位)

获得int型最小值

1
2
3
4
5
// @return -2147483647
int get_min_int()
{
    return 1 << 31;
}
1
1 << 31 = 10000000000000000000000000000000

获得long类型的最大值

1
2
3
4
5
// @return 9223372036854775807
long get_max_int()
{
    return ((unsigned long) - 1) >> 1;
}
1
((unsigned long) - 1) >> 1 = 111111111111111111111111111111111111111111111111111111111111111 (63位, long所能达到的最大位)

乘以2运算

1
2
3
4
int get_multiply_two(int numb)
{
    return numb << 1;
}
1
2
numb = 23 = 10111
10111 << 1 = 101110 = 46

除以2运算（这里仅作示例，针对偶数）

1
2
3
4
int get_divide_two(int numb)
{
    return numb >> 1;
}

>> 算术右移 A >> B 将 A 的二进制表示的每一位向右移 B 位，右边超出的位截掉，左边不足的位补符号位的数（比如负数符号位是1则补充1，正数符号位是0则补充0），so 对于算术右移，原负数结果还是负数，原正数的结果还是正数。[标注2]

1
2
numb = 24 = 11000
11000 >> 1 = 1100 = 12

乘以2的m次方

1
2
3
4
int get_multiply_party(int orginum, int m)
{
    return orginum << m;
}

return = orginum * 2m

1
2
3
orginum = 23 = 10111
m = 3
10111 << 3 = 10111000 = 184

除以2的m次方

1
2
3
4
int get_divide_party(int orginum, int m)
{
    return orginum >> m;
}

return = orginum / 2m

1
2
3
orginum = 56 = 111000
m = 3
111000 >> 3 = 111 = 7

判断一个数的奇偶性

1
2
3
4
int judge_parity(int numb)
{
    return (numb & 1) == 1;
}

按位与操作 A & B 将 A 和 B 的二进制表示的每一位进行与操作，只有两个对应的二进制位都为1时，结果位才为1，否则为0

1
2
3
4
5
6
7
8
9
10
11
numb = 20 = 10100
10100
00001
-----
00000 = 0 (偶数)
numb = 23 = 10111
10111
00001
-----
00001 = 1 (奇数)

不用临时变量交换两个数（面试常考）

1
2
3
4
5
6
void do_swap(int *param1, int *param2)
{
    *param1 ^= *param2;
    *param2 ^= *param1;
    *param1 ^= *param2;
}

按位异或操作 A ^ B 将A和B的二进制表示的每一位进行异或操作，如果对应的二进制位不同，结果位为1，否则为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
START:
param1 = 23 = 10111
param2 = 56 = 111000
// *param1 ^= *param2;
010111
111000
------
101111 = param1
// *param2 ^= *param1;
111000
101111
------
010111 = param2
// *param1 ^= *param2;
101111
010111
------
111000 = param1
END:
param1 = 111000 = 56
param2 = 010111 = 23

取绝对值（某些机器上，效率比 numb > 0 ? numb : -numb 高）

1
2
3
4
5
6
7
8
9
10
11
/*************************************************************************/
/* numb>>31 取得numb的符号 */
/* 若numb为正数，numb>>31等于0，若numb为负数，numb>>31等于-1 */
/* 若numb为正数 numb^0=0,数不变，若numb为负数有numb^-1 需要计算numb和-1的补码，然后进行异或运算， */
/* 结果numb变号并且为numb的绝对值减1，再减去-1就是绝对值 */
/*************************************************************************/
 
int get_abs(int numb)
{
    return (numb ^ (numb >> 31)) - (numb >> 31);
}
1
2
3
4
5
6
7
8
9
numb = 23 = 10111
numb >> 31 = 0
numb ^ (numb >> 31) = 10111
(numb ^ (numb >> 31)) - (numb >> 31) = 10111 = 23
numb = -23 = 11111111111111111111111111101001
numb >> 31 = 11111111111111111111111111111111
numb ^ (numb >> 31) = 00000000000000000000000000010110
(numb ^ (numb >> 31)) - (numb >> 31) = 10111 = 00000000000000000000000000010110 + (-11111111111111111111111111111111) = 10111 = 23

取两个数的最大值（某些机器上，效率比 numb1 > numb2 ? numb1 : numb2 高）

1
2
3
4
int get_max(int numb1, int numb2)
{
    return numb1 ^ ((numb1 ^ numb2) & -(numb1 < numb2));
}
1
2
3
4
5
6
numb1 = 23 = 010111
numb2 = 56 = 111000
numb1 ^ numb2 = 00000000000000000000000000101111
-(numb1 < numb2) = -1 = 11111111111111111111111111111111
(numb1 ^ numb2) & -(numb1 < numb2) = 101111
numb1 ^ ((numb1 ^ numb2) & -(numb1 < numb2)) = 111000 = 56

取两个数的最小值（某些机器上，效率比 numb1 < numb2 ? numb1 : numb2 高）

跟上面获取最大值类似

1
2
3
4
int get_min(int numb1, int numb2)
{
    return numb2 ^ ((numb1 ^ numb2) & -(numb1 < numb2));
}

1
2
3
4
5
6
numb1 = 23 = 010111
numb2 = 56 = 111000
numb1 ^ numb2 = 00000000000000000000000000101111
-(numb1 < numb2) = -1 = 11111111111111111111111111111111
(numb1 ^ numb2) & -(numb1 < numb2) = 101111
numb2 ^ ((numb1 ^ numb2) & -(numb1 < numb2)) = 010111 = 23

判断符号是否相同

1
2
3
4
int judge_same_symbol(int numb1, int numb2)
{
    return (numb1 ^ numb2) >= 0;
}
1
2
3
4
5
6
7
8
9
numb1 = 23 = 010111
numb2 = 56 = 111000
numb1 ^ numb2 = 101111
(numb1 ^ numb2) >= 0 = 1
numb1 = 23 = 00000000000000000000000000010111
numb2 = -23 = 
numb1 ^ numb2 = 101111
(numb1 ^ numb2) >= 0 = 1

判断一个数是不是2的幂

1
2
3
4
5
/* 如果是2的次幂, numb为 10000..., numb - 1 就是 1111..., 与操作就是0 */
int judge_two_power(int numb)
{
    return numb > 0 ? (numb & (numb - 1)) == 0 : 0;
}
1
2
3
4
5
6
7
numb = 56 = 111000
numb - 1 = 110111
(numb & (numb - 1)) = 110000 ≠ 0
numb = 64 = 1000000
numb - 1 = 0111111
(numb & (numb - 1)) = 0

二进制从低位到高位取，取 orginum 的第 numb 位

1
2
3
4
int get_binary_offset(int orginum, int numb)
{
    return (orginum >> (numb - 1)) & 1;
}
1
2
3
4
5
orginum = 111000
numb = 4
numb - 1 = 3
orginum >> (numb - 1) = 111
(orginum >> (numb - 1)) & 1 = 001 = 1

二进制从低位到高位取，将 orginum 的第 numb位 置为1

1
2
3
4
int do_binary_offset(int orginum, int numb)
{
    return orginum | (1 << (numb - 1));
}

按位或操作 A | B 将A和B的二进制表示的每一位进行或操作，只要两个对应的二进制位有一个为1，结果位就为1，否则为0

1
2
3
4
5
6
7
8
9
10
orginum = 111000
numb = 3
numb - 1 = 2
1 << (numb - 1) = 100
orginum | (1 << (numb - 1))：
111000
000100
-------
111100

二进制从低位到高位取，将 orginum 的第 numb位 置为0

1
2
3
4
int do_binary_offset(int orginum, int numb)
{
    return orginum & ~(1 << (numb-1));
}

按位非操作 A | B 将A的二进制表示每一位进行取反操作，如果对应的二进制位为0，结果位为1，否则为0，注意 这里是指一个位(bit)取反，对整数1取反结果不是0，因为整数1由32位(bit)组成。
比如十进制1， 表示成2进制是(00000000000000000000000000000001)2, 这里是32位有符号整数

1
2
3
4
5
6
7
8
9
10
11
orginum = 111000
numb = 4
numb - 1 = 3
1 << (numb - 1) = 00000000000000000000000000001000
~(1 << (numb - 1)) = 11111111111111111111111111110111
orginum & ~(1 << (numb-1))：
00000000000000000000000000111000
11111111111111111111111111110111
---------------------------------
00000000000000000000000000110000 = 110000

边角余料

下面的一些小技巧，感兴趣的童鞋可以用上面的知识尝试验证一下

1
2
3
4
5
6
7
8
/* 计算numb + 1 */
-~numb
/* 计算numb - 1 */
~-numb
/* 取相反数 */
~numb + 1

  • 标注1：那为什么不直接写成 A * 2 ^ B 呢？因为位移运算比乘法和求幂的运算快很多很多
  • 标注2：区别与 Java 特有的 逻辑右移 A >>> B：将 A 的二进制表示的每一位向右移 B 位，右边超出的位截掉，左边不足的位补 0，所以对于逻辑右移, 结果将会是一个正数。举个例子对于十进制数 -127 = 11111111111111111111111110000001，因为是负数，所以最高位上是1，逻辑右移的运算过程是：11111111111111111111111110000001 >> 2 = 00111111111111111111111111100000 = 1073741792

本文作者： wettper
本文链接： http://www.web-lovers.com/c-bit-operation.html
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

wettper <br /><br /> 现 离职状态 程序猿 <br /><br /> 叫醒我的不止阳光，还有梦想！<br /><br /> 喵喵、念念、健身、吉他！