位元運算與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脫衣器
Video Face Swap
使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
nginx在windows中怎麼配置
Apr 14, 2025 pm 12:57 PM
如何在 Windows 中配置 Nginx？安裝 Nginx 並創建虛擬主機配置。修改主配置文件並包含虛擬主機配置。啟動或重新加載 Nginx。測試配置並查看網站。選擇性啟用 SSL 並配置 SSL 證書。選擇性設置防火牆允許 80 和 443 端口流量。
docker怎麼啟動容器
Apr 15, 2025 pm 12:27 PM
Docker 容器啟動步驟：拉取容器鏡像：運行 "docker pull [鏡像名稱]"。創建容器：使用 "docker create [選項] [鏡像名稱] [命令和參數]"。啟動容器：執行 "docker start [容器名稱或 ID]"。檢查容器狀態：通過 "docker ps" 驗證容器是否正在運行。
docker容器名稱怎麼查
Apr 15, 2025 pm 12:21 PM
可以通過以下步驟查詢 Docker 容器名稱：列出所有容器（docker ps）。篩選容器列表（使用 grep 命令）。獲取容器名稱（位於 "NAMES" 列中）。
怎麼查看nginx是否啟動
Apr 14, 2025 pm 01:03 PM
確認 Nginx 是否啟動的方法：1. 使用命令行：systemctl status nginx（Linux/Unix）、netstat -ano | findstr 80（Windows）；2. 檢查端口 80 是否開放；3. 查看系統日誌中 Nginx 啟動消息；4. 使用第三方工具，如 Nagios、Zabbix、Icinga。
docker怎麼創建容器
Apr 15, 2025 pm 12:18 PM
在 Docker 中創建容器： 1. 拉取鏡像： docker pull [鏡像名] 2. 創建容器： docker run [選項] [鏡像名] [命令] 3. 啟動容器： docker start [容器名]
nginx怎麼查版本
Apr 14, 2025 am 11:57 AM
可以查詢 Nginx 版本的方法有：使用 nginx -v 命令；查看 nginx.conf 文件中的 version 指令；打開 Nginx 錯誤頁，查看頁面的標題。
nginx怎麼配置雲服務器域名
Apr 14, 2025 pm 12:18 PM
在雲服務器上配置 Nginx 域名的方法：創建 A 記錄，指向雲服務器的公共 IP 地址。在 Nginx 配置文件中添加虛擬主機塊，指定偵聽端口、域名和網站根目錄。重啟 Nginx 以應用更改。訪問域名測試配置。其他注意事項：安裝 SSL 證書啟用 HTTPS、確保防火牆允許 80 端口流量、等待 DNS 解析生效。
nginx服務器掛了怎麼辦
Apr 14, 2025 am 11:42 AM
當 Nginx 服務器宕機時，可執行以下故障排除步驟：檢查 nginx 進程是否正在運行。查看錯誤日誌以獲取錯誤消息。檢查 nginx 配置語法正確性。確保 nginx 具有訪問文件所需的權限。檢查文件描述符打開限制。確認 nginx 正在偵聽正確的端口。添加防火牆規則以允許nginx流量。檢查反向代理設置，包括後端服務器可用性。如需進一步幫助，請聯繫技術支持。
