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