位运算与nginx性能的联系
我们都知道nginx是以高性能出名的，这主要是归功于nginx的源码。本文我们就来讲讲位运算与nginx高性能的联系。
（学习视频分享：编程视频）
位运算在 Nginx 的源码是处处可见，从定义指令的类型（可以携带多少参数，可以出现在哪些配置块下），到标记当前请求是否还有未发送完的数据，再到 Nginx 事件模块里用指针的最低位来标记一个事件是否过期，无不体现着位运算的神奇和魅力。
本文会介绍和分析 Nginx 源码里的一些经典的位运算使用，并扩展介绍一些位其他的位运算技巧。
对齐
Nginx 内部在进行内存分配时，非常注意内存起始地址的对齐，即内存对齐（可以换来一些性能上的提升），这与处理器的寻址特性有关，比如某些处理器会按 4 字节宽度寻址，在这样的机器上，假设需要读取从 0x46b1e7 开始的 4 个字节，由于 0x46b1e7 并不处在 4 字节边界上（0x46b1e7 % 4 = 3），所以在进行读的时候，会分两次进行读取，第一次读取 0x46b1e4 开始的 4 个字节，并取出低 3 字节；再读取 0x46b1e8 开始的 4 个字节，取出最高的字节。我们知道读写主存的速度并不能匹配 CPU，那么两次的读取显然带来了更大的开销，这会引起指令停滞，增大 CPI（每指令周期数），损害应用程序的性能。
因此 Nginx 封装了一个宏，专门用以进行对齐操作。
#define ngx_align(d, a) (((d) + (a - 1)) & ~(a - 1))
如上代码所示，该宏使得 d 按 a 对齐，其中 a 必须是 2 的幂次。
比如 d 是 17，a 是 2 时，得到 18；d 是 15，a 是 4 时，得到 16；d 是 16，a 是 4 时，得到 16。
这个宏其实就是在寻找大于等于 d 的，第一个 a 的倍数。由于 a 是 2 的幂次， 因此 a 的二进制表示为 00...1...00 这样的形式，即它只有一个 1，所以 a - 1 便是 00...01...1 这样的格式，那么 ~(a - 1) 就会把低 n 位全部置为 0，其中 n 是 a 低位连续 0 的个数。所以此时如果我们让 d 和 ~(a - 1) 进行一次按位与操作，就能够把 d 的低 n 位清零，由于我们需要寻找大于等于 d 的数，所以用 d + (a - 1) 即可。
位图
位图，通常用以标记事物的状态，“位” 体现在每个事物只使用一个比特位进行标记，这即节约内存，又能提升性能。
Nginx 里有多处使用位图的例子，比如它的共享内存分配器（slab），再比如在对 uri（Uniform Resource Identifier）进行转义时需要判断一个字符是否是一个保留字符（或者不安全字符），这样的字符需要被转义成 %XX 。
static uint32_t uri_component[] = {
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
/* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
0xfc009fff, /* 1111 1100 0000 0000 1001 1111 1111 1111 */
/* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
0x78000001, /* 0111 1000 0000 0000 0000 0000 0000 0001 */
/* ~}| {zyx wvut srqp onml kjih gfed cba` */
0xb8000001, /* 1011 1000 0000 0000 0000 0000 0000 0001 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
};如上所示，一个简单的数组组成了一个位图，共包含 8 个数字，每个数字表示 32 个状态，因此这个位图把 256 个字符（包括了扩展 ASCII 码）。为 0 的位表示一个通常的字符，即不需要转义，为 1 的位代表的就需要进行转义。
那么这个位图该如何使用？Nginx 在遍历 uri 的时候，通过一条简单的语句来进行判断。
uri_component[ch >> 5] & (1U << (ch & 0x1f))
如上所示，ch 表示当前字符，ch >> 5 是对 ch 右移 5 位，这起到一个除以 32 的效果，这一步操作确定了 ch 在 uri_component 的第几个数字上；而右边的，(ch & 0x1f) 则是取出了 ch 低 5 位的值，相当于取模 32，这个值即表示 ch 在对应数字的第几个位（从低到高计算）；因此左右两边的值进行一次按位与操作后，就把 ch 字符所在的位图状态取出来了。比如 ch 是 '0'（即数字 48），它存在于位图的第 2 个数字上（48 >> 5 = 1），又在这个数字（0xfc009fff）的第 16 位上，所以它的状态就是 0xfc009fff & 0x10000 = 0，所以 '0'是一个通用的字符，不用对它转义。
从上面这个例子中我们还可以看到另外一个位运算的技巧，就是在对一个 2 的幂次的数进行取模或者除操作的时候，也可以通过位运算来实现，这比直接的除法和取模运算有着更好的性能，虽然在合适的优化级别下，编译器也可能替我们完成这样的优化。
寻找最低位 1 的位置
接着我们来介绍下一些其他的应用技巧。
找到一个数字二进制里最低位的 1 的位置，直觉上你也许会想到按位遍历，这种算法的时间复杂是 O(n)，性能上不尽如人意。
如果你曾经接触过树状数组，你可能就会对此有不同的看法，树状数组的一个核心概念是 计算 lowbit，即计算一个数字二进制里最低位 1 的幂次。它之所以有着不错的时间复杂度（O(logN)），便是因为能够在 O(1) 或者说常数的时间内得到答案。
int lowbit(int x)
{
return x & ~(x - 1);
}这个技巧事实上和上述对齐的方式类似，比如 x 是 00...111000 这样的数字，则 x - 1 就成了 00...110111，对之取反，则把原本 x 低位连续的 0 所在的位又重新置为了 0（而原本最低位 1 的位置还是为 1），我们会发现除了最低位 1 的那个位置，其他位置上的值和 x 都是相反的，因此两者进行按位与操作后，结果里只可能有一个 1，便是原本 x 最低位的 1。
寻找最高位 1 的位置
换一个问题，这次不是寻找最低位，而是寻找最高位的 1。
这个问题有着它实际的意义，比如在设计一个 best-fit 的内存池的时候，我们需要找到一个比用户期望的 size 大的第一个 2 的幂次。
同样地，你可能还是会先想到遍历。
事实上 Intel CPU 指令集有这么一条指令，就是用以计算一个数二进制里最高位 1 的位置。
size_t bsf(size_t input)
{
size_t pos;
__asm__("bsfq %1, %0" : "=r" (pos) : "rm" (input));
return pos;
}这很好，但是这里我们还是期望用位运算找到这个 1 的位置。
size_t bsf(size_t input)
{
input |= input >> 1;
input |= input >> 2;
input |= input >> 4;
input |= input >> 8;
input |= input >> 16;
input |= input >> 32;
return input - (input >> 1);
}这便是我们所期望的计算方式了。我们来分析下这个计算的原理。
需要说明的是，如果你需要计算的值是 32 位的，则上面函数的最后一步 input |= input >> 32 是不需要的，具体执行多少次 input |= input >> m， 是由 input 的位长决定的，比如 8 位则进行 3 次，16 位进行 4 次，而 32 位进行 5 次。
为了更简洁地进行描述，我们用 8 位的数字进行分析，设一个数 A，它的二进制如下所示。
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
上面的计算过程如下。
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] 0 A[7] A[6] A[5] A[4] A[3] A[2] A[1] --------------------------------------- A[7] A[7]|A[6] A[6]|A[5] A[5]|A[4] A[4]|A[3] A[3]|A[2] A[2]|A[1] A[1]|A[0] 0 0 A[7] A[7]|A[6] A[6]|A[5] A[5]|A[4] A[4]|A[3] A[3]|A[2] -------------------------------------------------------------------------- A[7] A[7]|A[6] A[7]|A[6]|A[5] A[7]|A[6]|A[5]|A[4] A[6]|A[5]|A[4]|A[3] A[5]|A[4]|A[3]|A[2] A[4]|A[3]|A[2]|A[1] A[3]|A[2]|A[1]|A[0] 0 0 0 0 A[7] A[7]|A[6] A[7]|A[6]|A[5] A[7]|A[6]|A[5]|A[4] --------------------------------------------------------------------------------------------------------------------------------- A[7] A[7]|A[6] A[7]|A[6]|A[5] A[7]|A[6]|A[5]|A[4] A[7]|A[6]|A[5]|A[4]|A[3] A[7]|A[6]|A[5]|A[4]|A[3]|A[2] A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1] A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1]|A[0]
我们可以看到，最终 A 的最高位是 A[7]，次高位是 A[7]|A[6]，第三位是 A[7]|A[6]|A[5]，最低位 A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1]|A[0]
假设最高位的 1 是在第 m 位（从右向左算，最低位称为第 0 位），那么此时的低 m 位都是 1，其他的高位都是 0。也就是说，A 将会是 2 的某幂再减一，于是最后一步（input - (input >> 1)）的用意也就非常明显了，即将除最高位以外的 1 全部置为 0，最后返回的便是原来的 input 里最高位 1 的对应幂了。
计算 1 的个数
如何计算一个数字二进制表示里有多少个 1 呢？
直觉上可能还是会想到遍历（遍历真是个好东西），让我们计算下复杂度，一个字节就是 O(8)，4 个字节就是 O(32)，而 8 字节就是 O(64)了。
如果这个计算会频繁地出现在你的程序里，当你在用 perf 这样的性能分析工具观察你的应用程序时，它或许就会得到你的关注，而你不得不去想办法进行优化。
事实上《深入理解计算机系统》这本书里就有一个这个问题，它要求计算一个无符号长整型数字二进制里 1 的个数，而且希望你使用最优的算法，最终这个算法的复杂度是 O(8)。
long fun_c(unsigned long x)
{
long val = 0;
int i;
for (i = 0; i < 8; i++) {
val += x & 0x0101010101010101L;
x >>= 1;
}
val += val >> 32;
val += val >> 16;
val += val >> 8;
return val & 0xFF;
}这个算法在我的另外一篇文章里曾有过分析。
观察 0x0101010101010101 这个数，每 8 位只有最后一位是 1。那么 x 与之做按位与，会得到下面的结果：
设 A[i] 表示 x 二进制表示里第 i 位的值（0 或 1）。 第一次： A[0] + (A[8] << 8) + (A[16] << 16) + (A[24] << 24) + (A[32] << 32) + (A[40] << 40) + (A[48] << 48) + (A[56] << 56) 第二次： A[1] + (A[9] << 8) + (A[17] << 16) + (A[25] << 24) + (A[33] << 32) + (A[41] << 40) + (A[49] << 48) + (A[57] << 56) ...... 第八次： A[7] + (A[15] << 8) + (A[23] << 16) + (A[31] << 24) + (A[39] << 32) + (A[47] << 40) + (A[55] << 48) + (A[63] << 56) 相加后得到的值为： (A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 56 + (A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48]) << 48 + (A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40]) << 40 + (A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32]) << 32 + (A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24]) << 24 + (A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16]) << 16 + (A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8]) << 8 + (A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0])
之后的三个操作：
val += val >> 32; val += val >> 16; val += val >> 8;
每次将 val 折半然后相加。
第一次折半（val += val >> 32）后，得到的 val 的低 32 位：
(A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24] + A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 24 + (A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16] + A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48]) << 16 + (A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8] + A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40]) << 8 + (A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0] + A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32])
第二次折半（val += val >> 16）后，得到的 val 的低 16 位：
15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8] + A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40] + A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24] + A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 8 + (A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0] + A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32] + A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16] + A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48])
第三次折半（val += val >> 8）后，得到的 val 的低 8 位：
(A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0] + A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32] + A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16] + A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48] + A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8] + A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40] + A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24] + A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56])
可以看到，经过三次折半，64 个位的值全部累加到低 8 位，最后取出低 8 位的值，就是 x 这个数字二进制里 1 的数目了，这个问题在数学上称为“计算汉明重量”。
位运算以它独特的优点（简洁、性能棒）吸引着程序员，比如 LuaJIT 内置了 bit 这个模块，允许程序员在 Lua 程序里使用位运算。学会使用位运算对程序员来说也是一种进步，值得我们一直去研究。
相关推荐：nginx教程
以上是位运算与nginx性能的联系的详细内容。更多信息请关注PHP中文网其他相关文章！
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
AI Hentai Generator
免费生成ai无尽的。
热门文章
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
热门话题
不同Java框架的性能对比
Jun 05, 2024 pm 07:14 PM
不同Java框架的性能对比：RESTAPI请求处理：Vert.x最佳，请求速率达SpringBoot2倍，Dropwizard3倍。数据库查询：SpringBoot的HibernateORM优于Vert.x及Dropwizard的ORM。缓存操作：Vert.x的Hazelcast客户机优于SpringBoot及Dropwizard的缓存机制。合适框架：根据应用需求选择，Vert.x适用于高性能Web服务，SpringBoot适用于数据密集型应用，Dropwizard适用于微服务架构。
C++中如何优化多线程程序的性能？
Jun 05, 2024 pm 02:04 PM
优化C++多线程性能的有效技术包括：限制线程数量，避免争用资源。使用轻量级互斥锁，减少争用。优化锁的范围，最小化等待时间。采用无锁数据结构，提高并发性。避免忙等，通过事件通知线程资源可用性。
C++与其他语言的性能比较
Jun 01, 2024 pm 10:04 PM
在开发高性能应用程序时，C++的性能优于其他语言，尤其在微基准测试中。在宏基准测试中，其他语言如Java和C#的便利性和优化机制可能表现更好。在实战案例中，C++在图像处理、数值计算和游戏开发中表现出色，其对内存管理和硬件访问的直接控制带来明显的性能优势。
Golang 中随机数生成器的性能如何？
Jun 01, 2024 pm 09:15 PM
在Go中生成随机数的最佳方法取决于应用程序所需的安全性级别。低安全性：使用math/rand包生成伪随机数字，适合大多数应用程序。高安全性：使用crypto/rand包生成加密安全的随机字节，适用于需要更强随机性的应用程序。
Java框架的性能比较
Jun 04, 2024 pm 03:56 PM
根据基准测试，对于小型、高性能应用程序，Quarkus（快速启动、低内存）或Micronaut（TechEmpower优异）是理想选择。SpringBoot适用于大型、全栈应用程序，但启动时间和内存占用稍慢。
WordPress站点文件访问受限：为什么我的.txt文件无法通过域名访问？
Apr 01, 2025 pm 03:00 PM
Wordpress站点文件访问受限：排查.txt文件无法访问的原因最近有用户在配置小程序业务域名时，遇到一个问题：�...
如何在同一台服务器上通过Nginx配置让PHP5.6和PHP7共存？
Apr 01, 2025 pm 03:15 PM
在同一系统中同时运行多个PHP版本是一个常见的需求，特别是当不同项目依赖于不同版本的PHP时。如何在同一台...
如何在LAMP架构下高效整合Node.js或Python服务？
Apr 01, 2025 pm 02:48 PM
在LAMP架构下整合Node.js或Python服务许多网站开发者都面临这样的问题：已有的LAMP(Linux Apache MySQL PHP)架构网站需要...
