位运算实用指南

让程序员能够在更高层的维度思考,这似乎一直是软件开发的发展方向,但偏向底层的实现(优化)似乎也从未离开过程序员们的视野,位运算便是其中一个编程话题~ 下文列出的一些位运算代码实例,个人觉得还是偏于实践的,故以”实用指南”为题,姑且算作是一篇笔记,也希望可以给有兴趣的朋友一些参考~ 如无特别说明,位操作的源操作数类型皆为 整型 ,并且也不考虑 负数溢出 等情况

基础篇

代码:

// C#
int multiply_2_power_n(int val, int n)
{
    // val * (2 power n)
    return val << n;
}

// C#
int divide_2_power_n(int val, int n)
{
    // val / (2 power n)
    return val >> n;
}

效果 : 乘以2的n次幂/除以2的n次幂

说明 : 想来这应该是初次接触移位操作符时一定会了解到的知识点,根据2进制的整数表示方法应该不难理解,原因细节不再赘述~


代码:

// C#
int get_bit(int val, int n)
{
    // get val's n-th bit
    return val & (1 << n);
}

// C#
int set_bit(int val, int n)
{
    // set val's n-th bit to 1
    return val | (1 << n);
}

// C#
int clear_bit(int val, int n)
{
    // set val's n-th bit to 0
    return val & (~(1 << n));
}

效果 : 获取/设置/清空数值的某一位

说明 : 上述应该算是平时工作中最常用的位方法了,当我们需要标记对象的一些正交属性时往往会使用他们~

另外,上述代码中的 set_bit 和 clear_bit 可以合并成一个方法,这样接口上更加简洁些:

// C#
int update_bit(int val, int n, int s)
{
    // update val's n-th bit to s (s should be 1 or 0)
    return (val & (~(1 << n))) | (s << n);
}

有时候我们可能还需要位数值的 toggle 操作,可以使用异或(^)操作来实现:

// C#
int toggle_bit(int val, int n)
{
    // toggle val's n-th bit
    return val ^ (1 << n);
}

我们也可以批量清除连续位的数值:

// C#
int clear_bits_to_n(int val, int n)
{
    // clear bits from top(msb) to n
    return val & ((1 << n) - 1);
}

// C#
int clear_bits_from_n_1(int val, int n)
{
    // clear bits from n - 1 to 0(lsb)
    return val & (~((1 << n) - 1));
}

这里的技巧是对移位之后的数值进行减1操作,这样可以构造一个类似于0*1*(譬如0x0000FFFF)的位结构,之后便可以借助这个位结构来进行批量的位数值操作了~

类似的技巧也可以用于计算模2的n次幂 :

// C#
int modulus_power_of_2(int val, int n)
{
    // val % (2 power n)
    return val & ((1 << n) - 1);
}

有趣的是上面的代码实现与之前的 clear_bits_to_n 方法是一样的,因为他们解决的其实是一个问题,只是表述不同罢了~

进阶篇

代码:

// C#
bool is_even(int val)
{
    // check whether val is even
    return (val & 1) == 0;
}

// C#
bool is_odd(int val)
{
    // check whether val is odd
    return (val & 1) == 1;
}

效果 : 判断一个数是否为偶数/奇数

说明 : 比起传统的通过 模(%)2 方式来判断数值奇偶的方法,上面这种直接通过判断二进制最低位是否为1的方法来的更加简洁高效一些

这里稍稍发散下,我们来考虑下二进制的最高位(注意,这里我们考虑了负数情况)~

// C#
int get_sign(int val)
{
    // get val's sign
    return (val >> 31) & 1;
}

上述代码用于获取数值的符号位大小,比起一般的方法少了分支判断(代码中最后的 & 1 操作涉及算术移位的知识,可以点击这里了解)~

// C#
int get_sign(int val)
{
    // normal way to get val's sign
    return val >= 0 ? 0 : 1;
}

代码:

// C#
bool is_power_of_2(int val)
{
    // check whether val is power of 2
    return (val & (val - 1)) == 0;
}

效果 : 判断数值是否为2的幂

说明 :

这里利用了2的幂的二进制表示中只有最高位为1的特性,举个简单的例子:

假设 val 的二进制表示为 1000 (即十进制中的 8)

则有 val - 1 的二进制为 0111 (即十进制中的 7)

则有 val & (val - 1) = 1000 & 0111 = 0

其他非2的幂的数值则不满足这个运算特性,有些意外的是,上述计算过程也会将 0 判断为是2的幂,我们可以在原先逻辑中加入是否为 0 的判断来使代码更健壮些~

// C#
bool is_power_of_2(int val)
{
    // check whether val is power of 2
    return ((val & (val - 1)) == 0) && (val != 0);
}

除了判断一个数值是否为2的幂以外,实际开发中我们可能还需要计算与一个数值 “接近” 的2的幂大小,譬如给定数值 17, 与其最”接近”的2的幂大小即为 16,下面的代码可以计算不大于给定数值的最大的2的幂:

// C#
int floor_power_of_2(int val)
{
    // calc power of 2 which <= val
    val |= (val >> 1);
    val |= (val >> 2);
    val |= (val >> 4);
    val |= (val >> 8);
    val |= (val >> 16);
    return val - (val >> 1);
}

上述代码初看上去可能有些费解,但其实基本思路很简单:将数值的最高位上的 1 “传播”至之后的所有位上~

说的有些抽象,来看一个具体实例:

假设 val 的二进制表示为 10010100 (即十进制中的 148)

执行 val |= (val >> 1),这个操作可以将最高位的 1 传播 至最高位的后一位上,至于其他位上的数值变化我们可以不关心,于是 val 经过这步操作,二进制表示变成了这样 : 11****** (*号代表我们目前不关心该位上的数值变化)

好了,按照上述思路,我们本可以继续执行 val |= (val >> 1)“传播” 最高位上的 1,但是由于我们已经知道经过第一步操作后, val 的头两位都是 1, 所以我们可以一次性移动两位来加快这个 “传播” 过程,于是我们便有了源码中的第二步操作 : val |= (val >> 2)

后面的几步操作基本都是这个思路,所以移位操作的最后, val 的二进制表示变成了这样 : 11111111

这时我们将最高位以外的 1 去除,便得到了不大于 val 的2的幂 : val - (val >> 1)

计算不小于给定数值的2的幂也是类似方法:

// C#
int ceil_power_of_2(int val)
{
    // calc power of 2 which >= val
    val -= 1;
    val |= (val >> 1);
    val |= (val >> 2);
    val |= (val >> 4);
    val |= (val >> 8);
    val |= (val >> 16);
    val += 1;
    return val;
}

稍有技巧的地方就是一开始对 val 的减 1 操作和最后的加 1 操作,其他的代码与计算不大于给定数值的2的幂的逻辑是相同的~

有了关于2的幂的 “底”函数(floor_power_of_2)“顶”函数(ceil_power_of_2),我们就可以计算最接近给定值的2的幂了:

// C#
int closest_power_of_2(int val)
{
    var ceil = ceil_power_of_2(val);
    var floor = floor_power_of_2(val);
    return val - floor < ceil - val ? floor : ceil;
}

这里可以做一个简单的优化,我们得到”顶”函数的结果之后,可以通过右移的方式来获取前一个2的幂的数值,虽然这个数值不一定等于”底”函数的结果,但仍然可以配合”顶”函数来计算最接近给定值的2的幂:

// C#
int closest_power_of_2(int val)
{
    var ceil = ceil_power_of_2(val);
    var floor = ceil >> 1;
    return val - floor < ceil - val ? floor : ceil;
}

更多篇

常见的 min,max 函数也有位运算的版本,可以避免分支判断:

// C#
int min(int a, int b)
{
    var mask = (a - b) >> 31;
    return (a & mask) | (b & ~mask);
}

// C#       
int max(int a, int b)
{
    var mask = (a - b) >> 31;
    return (b & mask) | (a & ~mask);
}

这里的技巧是根据 a 与 b 差值的符号位来构造掩码(再提一下,这里的逻辑操作涉及算术移位的知识,可以点击这里了解)

有了 min 和 max,我们就可以实现无分支的 clamp 函数了:

// C#
int clamp(int val, int min_val, int max_val)
{
    return min(max(val, min_val), max_val);
}

不少书籍都提到过不使用临时变量的swap函数,其中就有位运算版本:

// C#
void swap(ref int a, ref int b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

abs函数的一个位运算版本(可以参考这里进一步了解):

// C#
int abs(int v)
{
    var mask = v >> 31;
    return (v + mask) ^ mask;
}

一般的三元条件运算符(?:)也可以使用位运算实现:

// C#
int if_c_then_a_else_b(int c, int a, int b)
{
    // c <= 0 means false, > 0 means true
    return ((-c >> 31) & (a ^ b)) ^ b;
}

如果条件运算符中的 b 恒为 0 的话,我们还可以简化实现:

// C#
int if_c_then_a_else_0(int c, int a)
{
    // c <= 0 means false, > 0 means true
    return (-c >> 31) & a;
}

网络编程中往往会涉及大端序和小端序的相互转换,考虑以下代码:

// C#
uint revert_bits(uint val)
{
    val = ((val & 0x55555555) << 1) | ((val & 0xAAAAAAAA) >> 1);
    val = ((val & 0x33333333) << 2) | ((val & 0xCCCCCCCC) >> 2);
    val = ((val & 0x0F0F0F0F) << 4) | ((val & 0xF0F0F0F0) >> 4);
    val = ((val & 0x00FF00FF) << 8) | ((val & 0xFF00FF00) >> 8);
    val = ((val & 0x0000FFFF) << 16) | ((val & 0xFFFF0000) >> 16);
    return val;
}

这段代码运用了二分法的思想,首先将相邻2位交换,然后以2位一组进行交换,接着以4位一组进行交换,直到以16位一组进行交换后,所有位便都交换完成了~

不过在大小端转换时我们可能并不需要把单个字节的位值也翻转过来,这时只要直接以8位一组开始交换即可:

// C#
uint revert_bytes(uint val)
{
    val = ((val & 0x00FF00FF) << 8) | ((val & 0xFF00FF00) >> 8);
    val = ((val & 0x0000FFFF) << 16) | ((val & 0xFFFF0000) >> 16);
    return val;
}

简单写了一些位运算的东西,文字虽不短,但其实涉及的内容并不多,有兴趣的朋友可以在这里看到更多内容:

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

很早之前就有人开始记录总结位运算技巧了(github上有个更好读的md版本) :

http://graphics.stanford.edu/~seander/bithacks.html

对于位运算话题非常有兴趣的朋友可以继续看看Hack’s Delight~


相关的示例代码可以在github上找到~

我的博客即将搬运同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=37tqmkea2rwg4

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java成神之路

计算字符串相似度算法——Levenshtein

Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。

8491
来自专栏算法channel

程序员必知的算法和数据结构:2500字性能总结

以下5个步骤总结了此方法,依次为如下,我们设计的实验必须是可以重现的,我们形成的假设必须是具有真伪的。

760
来自专栏PPV课数据科学社区

R与数据分析学习总结之一:R语言基本操作

? 最近开始学习R语言,把学习笔记和小伙伴们分享一下吧,欢迎一起交流 R 起源: R是S语言的一种实现。S语言是由 AT&T贝尔实验室开发的一种用来进行数据探...

6206
来自专栏C语言及其他语言

[每日一题]矩阵乘法

本次的题目来源于C语言网比赛栏目八月月赛第一题,记得去试试看看自己能不能AC哦!!! 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: ...

3575
来自专栏机器学习算法工程师

一道网易笔试题引发的血案……

作者:柳行刚 编辑:黄俊嘉 网易的2016年笔试题,题目经典。 所以特地找来给各位有兴趣的童鞋看看, 有详细的解题思路以及代码喔~ 各位,请看题! 题目描述: ...

46612
来自专栏Linyb极客之路

UML类图(下):关联、聚合、组合、依赖

关联(Assocition)关系是类与类之间最常见的一种关系,它是一种结构化的关系,表示一类对象与另一类对象之间有联系,如汽车和轮胎、师傅和徒弟、班级和学生等。...

1572
来自专栏机器学习算法与Python学习

Python中的实用小技巧

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 话说python是一个大杂会,既可以...

3465
来自专栏androidBlog

快速排序的相关算法题(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

2391
来自专栏小詹同学

Leetcode打卡 | No.012 整数转罗马数字

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1211
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K5

扫码关注云+社区

领取腾讯云代金券