位图操作实际应用场景详解

张

张建站

2026/6/2 16:57:37

10分钟阅读

1. 操作系统和内存管理1.1 伙伴系统Buddy System内存分配场景描述操作系统需要高效管理物理内存伙伴系统是最经典的算法之一。#define PAGE_SIZE 4096 // 4KB页 #define MAX_ORDER 10 // 最大2^10 1024页连续 #define TOTAL_PAGES (1 MAX_ORDER) struct buddy_system { unsigned int free_lists[MAX_ORDER 1][MAX_ORDER 1]; // 空闲链表 unsigned long page_map[TOTAL_PAGES / 64]; // 位图管理页状态 }; // 查找连续页块 int buddy_alloc(struct buddy_system *bs, int order) { for (int current_order order; current_order MAX_ORDER; current_order) { if (bs-free_lists[current_order][0] ! 0) { // 找到合适大小的块 int block bs-free_lists[current_order][0]; // 如果块太大需要分裂 while (current_order order) { current_order--; // 分裂一分为二 int buddy block ^ (1 current_order); // 关键用异或找伙伴 // 将伙伴块加入空闲链表 bs-free_lists[current_order][bs-free_lists[current_order][0]] buddy; } // 标记块已使用 int word_idx block / 64; int bit_idx block % 64; bs-page_map[word_idx] | (1UL bit_idx); return block; } } return -1; // 分配失败 } // 释放内存 void buddy_free(struct buddy_system *bs, int block, int order) { int word_idx block / 64; int bit_idx block % 64; // 清除使用标记 bs-page_map[word_idx] ~(1UL bit_idx); // 尝试合并伙伴 while (order MAX_ORDER) { int buddy block ^ (1 order); // 异或快速找到伙伴块 // 检查伙伴是否空闲 word_idx buddy / 64; bit_idx buddy % 64; if (bs-page_map[word_idx] (1UL bit_idx)) { break; // 伙伴被占用停止合并 } // 从空闲链表中移除伙伴 for (int i 1; i bs-free_lists[order][0]; i) { if (bs-free_lists[order][i] buddy) { bs-free_lists[order][i] bs-free_lists[order][bs-free_lists[order][0]--]; break; } } // 合并取两个块中较小的地址 block block buddy; // AND操作找到合并后的起始地址 order; } // 将合并后的块加入空闲链表 bs-free_lists[order][bs-free_lists[order][0]] block; }位运算亮点block ^ (1 order)异或快速找到伙伴块地址block buddyAND操作获取合并后的起始地址1.2 页表项Page Table Entry标志位场景描述CPU内存管理单元(MMU)使用页表项控制内存访问。// x86架构页表项标志位 #define PTE_PRESENT (1 0) // 页在内存中 #define PTE_WRITABLE (1 1) // 可写 #define PTE_USER (1 2) // 用户态可访问 #define PTE_WRITETHROUGH (1 3) // 写穿透 #define PTE_CACHE_DISABLE (1 4) // 禁用缓存 #define PTE_ACCESSED (1 5) // 已访问 #define PTE_DIRTY (1 6) // 已修改 #define PTE_PAT (1 7) // 页属性表 #define PTE_GLOBAL (1 8) // 全局页 #define PTE_NX (1UL 63) // 不可执行64位 typedef unsigned long pte_t; // 创建页表项 pte_t make_pte(unsigned long phys_addr, int flags) { // 物理地址需要12位对齐低12位用于标志 pte_t pte phys_addr ~0xFFF; // 清除低12位 // 设置标志位 pte | flags; return pte; } // 检查页属性 int is_page_present(pte_t pte) { return pte PTE_PRESENT; } int is_page_dirty(pte_t pte) { return pte PTE_DIRTY; } // 修改页属性 void set_page_writable(pte_t *pte, int writable) { if (writable) { *pte | PTE_WRITABLE; } else { *pte ~PTE_WRITABLE; } } // 清除已访问标志硬件会设置这个位 void clear_accessed(pte_t *pte) { *pte ~PTE_ACCESSED; } // 页错误处理 void page_fault_handler(pte_t *pte, unsigned long fault_addr) { if (!(*pte PTE_PRESENT)) { // 页不在内存中需要从磁盘加载 load_page_from_swap(fault_addr); *pte | PTE_PRESENT; // 设置存在位 } if (fault_addr 0x1) { // 检查错误码最低位 // 写操作导致的错误 if (!(*pte PTE_WRITABLE)) { // 尝试写时复制COW if (*pte PTE_DIRTY) { cow_page(pte); } } } *pte | PTE_ACCESSED; // 标记为已访问 }2. 网络协议2.1 IP首部处理场景描述网络数据包处理需要高效操作二进制协议头。// IP首部结构通常20字节 struct ip_header { unsigned char ver_ihl; // 版本(4位) 首部长度(4位) unsigned char tos; // 服务类型 unsigned short total_len; // 总长度 unsigned short id; // 标识 unsigned short frag_off; // 标志(3位) 片偏移(13位) unsigned char ttl; // 生存时间 unsigned char protocol; // 协议 unsigned short checksum; // 首部校验和 unsigned int src_addr; // 源IP unsigned int dest_addr; // 目的IP }; // 提取版本号 int get_ip_version(unsigned char ver_ihl) { return (ver_ihl 4) 0x0F; // 高4位 } // 提取首部长度单位4字节 int get_ihl(unsigned char ver_ihl) { return ver_ihl 0x0F; // 低4位 } // 设置版本号和首部长度 void set_ver_ihl(struct ip_header *ip, int version, int ihl) { ip-ver_ihl (version 4) | (ihl 0x0F); } // 解析分片信息 struct frag_info { int reserved; // 保留位 int df; // 不分片标志 int mf; // 更多分片标志 int offset; // 片偏移 }; struct frag_info parse_frag(unsigned short frag_off) { struct frag_info info; info.reserved (frag_off 15) 0x01; info.df (frag_off 14) 0x01; info.mf (frag_off 13) 0x01; info.offset frag_off 0x1FFF; // 低13位 return info; } // 计算IP校验和16位反码和 unsigned short ip_checksum(void *header, int len) { unsigned short *buf (unsigned short *)header; unsigned long sum 0; for (int i 0; i len / 2; i) { sum buf[i]; // 处理进位 if (sum 0xFFFF0000) { sum 0xFFFF; sum; } } // 返回反码 return ~(sum 0xFFFF); }2.2 TCP标志位处理场景描述TCP协议有多个标志位需要快速检查。#define TCP_FIN (1 0) // 结束 #define TCP_SYN (1 1) // 同步 #define TCP_RST (1 2) // 重置 #define TCP_PSH (1 3) // 推送 #define TCP_ACK (1 4) // 确认 #define TCP_URG (1 5) // 紧急 #define TCP_ECE (1 6) // ECN回显 #define TCP_CWR (1 7) // 拥塞窗口减少 // TCP状态机 struct tcp_connection { int state; unsigned char flags; // ... 其他字段 }; // 处理收到的TCP段 void tcp_input(struct tcp_connection *conn, unsigned char flags) { // 检查是否有SYN标志 if (flags TCP_SYN) { if (conn-state LISTEN) { conn-state SYN_RECEIVED; send_packet(TCP_SYN | TCP_ACK); } else if (conn-state SYN_SENT) { conn-state ESTABLISHED; } } // 检查是否是ACK响应 if (flags TCP_ACK) { if (conn-state SYN_RECEIVED) { conn-state ESTABLISHED; } else if (conn-state FIN_WAIT_1) { conn-state FIN_WAIT_2; } } // 检查FIN标志连接关闭 if (flags TCP_FIN) { conn-state CLOSE_WAIT; send_packet(TCP_ACK); send_packet(TCP_FIN); } // 检查RST标志异常终止 if (flags TCP_RST) { conn-state CLOSED; cleanup_connection(conn); } // 检查URG标志紧急数据 if (flags TCP_URG) { process_urgent_data(); } // 多标志组合判断 if ((flags (TCP_SYN | TCP_ACK)) (TCP_SYN | TCP_ACK)) { // 这是SYN-ACK响应 handle_syn_ack(); } if (flags (TCP_FIN | TCP_RST)) { // 连接即将关闭或已重置 mark_connection_closing(); } }3. 图形图像处理3.1 颜色空间转换场景描述视频处理需要快速转换颜色空间。// YUV转RGB视频编码常用 struct rgb { unsigned char r, g, b; }; struct yuv { unsigned char y, u, v; }; // 快速YUV转RGB使用整数运算 struct rgb yuv_to_rgb_fast(struct yuv yuv) { struct rgb rgb; int c, d, e; // YUV范围调整 c yuv.y - 16; d yuv.u - 128; e yuv.v - 128; // 转换公式整数版本 rgb.r (298 * c 409 * e 128) 8; rgb.g (298 * c - 100 * d - 208 * e 128) 8; rgb.b (298 * c 516 * d 128) 8; // 钳位到0-255 rgb.r rgb.r 255 ? 255 : (rgb.r 0 ? 0 : rgb.r); rgb.g rgb.g 255 ? 255 : (rgb.g 0 ? 0 : rgb.g); rgb.b rgb.b 255 ? 255 : (rgb.b 0 ? 0 : rgb.b); return rgb; } // 批量转换SIMD风格优化 void yuv_to_rgb_batch(struct yuv *yuv_data, struct rgb *rgb_data, int count) { for (int i 0; i count; i) { // 直接操作32位整数 unsigned int y yuv_data[i].y; unsigned int u yuv_data[i].u; unsigned int v yuv_data[i].v; // 同时计算RGB实际可展开为SIMD指令 unsigned int r (298 * (y - 16) 409 * (v - 128) 128) 8; unsigned int g (298 * (y - 16) - 100 * (u - 128) - 208 * (v - 128) 128) 8; unsigned int b (298 * (y - 16) 516 * (u - 128) 128) 8; // 打包成32位RGB rgb_data[i] (r 16) | (g 8) | b; } }3.2 图像混合特效场景描述视频编辑软件需要实现各种混合模式。// 混合模式枚举 enum blend_mode { BLEND_NORMAL, // 正常 BLEND_MULTIPLY, // 正片叠底 BLEND_SCREEN, // 滤色 BLEND_OVERLAY, // 叠加 BLEND_DIFFERENCE // 差值 }; // 通用像素混合器 unsigned int blend_pixels(unsigned int bg, unsigned int fg, unsigned char alpha, enum blend_mode mode) { unsigned char br (bg 16) 0xFF; unsigned char bg (bg 8) 0xFF; unsigned char bb bg 0xFF; unsigned char fr (fg 16) 0xFF; unsigned char fg (fg 8) 0xFF; unsigned char fb fg 0xFF; unsigned char result_r, result_g, result_b; switch (mode) { case BLEND_MULTIPLY: // 正片叠底C A * B / 255 result_r (br * fr) 8; result_g (bg * fg) 8; result_b (bb * fb) 8; break; case BLEND_SCREEN: // 滤色C 255 - (255-A)*(255-B)/255 result_r 255 - ((255 - br) * (255 - fr) 8); result_g 255 - ((255 - bg) * (255 - fg) 8); result_b 255 - ((255 - bb) * (255 - fb) 8); break; case BLEND_OVERLAY: // 叠加根据背景决定 result_r br 128 ? (2 * br * fr) 8 : 255 - (2 * (255 - br) * (255 - fr) 8); result_g bg 128 ? (2 * bg * fg) 8 : 255 - (2 * (255 - bg) * (255 - fg) 8); result_b bb 128 ? (2 * bb * fb) 8 : 255 - (2 * (255 - bb) * (255 - fb) 8); break; case BLEND_DIFFERENCE: // 差值C |A - B| result_r br fr ? br - fr : fr - br; result_g bg fg ? bg - fg : fg - bg; result_b bb fb ? bb - fb : fb - bb; break; default: // 正常混合 result_r fr; result_g fg; result_b fb; } // 应用透明度 if (alpha 255) { result_r (result_r * alpha br * (255 - alpha)) 8; result_g (result_g * alpha bg * (255 - alpha)) 8; result_b (result_b * alpha bb * (255 - alpha)) 8; } return (result_r 16) | (result_g 8) | result_b; }4. 嵌入式系统4.1 寄存器操作场景描述嵌入式开发中需要直接操作硬件寄存器。// GPIO寄存器定义以STM32为例 #define GPIOA_BASE 0x40010800 #define GPIOA_CRL *(volatile unsigned int*)(GPIOA_BASE 0x00) // 配置低寄存器 #define GPIOA_CRH *(volatile unsigned int*)(GPIOA_BASE 0x04) // 配置高寄存器 #define GPIOA_IDR *(volatile unsigned int*)(GPIOA_BASE 0x08) // 输入数据 #define GPIOA_ODR *(volatile unsigned int*)(GPIOA_BASE 0x0C) // 输出数据 #define GPIOA_BSRR *(volatile unsigned int*)(GPIOA_BASE 0x10) // 置位/复位 // 引脚模式定义 #define GPIO_MODE_INPUT 0x0 // 输入 #define GPIO_MODE_OUTPUT_10 0x1 // 输出最大10MHz #define GPIO_MODE_OUTPUT_2 0x2 // 输出最大2MHz #define GPIO_MODE_OUTPUT_50 0x3 // 输出最大50MHz #define GPIO_CNF_INPUT_ANALOG 0x0 // 模拟输入 #define GPIO_CNF_INPUT_FLOATING 0x1 // 浮空输入 #define GPIO_CNF_INPUT_PUPD 0x2 // 上拉/下拉输入 #define GPIO_CNF_OUTPUT_PUSHPULL 0x0 // 推挽输出 #define GPIO_CNF_OUTPUT_OPENDRAIN 0x1 // 开漏输出 #define GPIO_CNF_OUTPUT_AF_PP 0x2 // 复用推挽 #define GPIO_CNF_OUTPUT_AF_OD 0x3 // 复用开漏 // 配置GPIO引脚 void gpio_config(int port, int pin, int mode, int conf) { volatile unsigned int *cr; int shift; // 选择配置寄存器低8位或高8位 if (pin 8) { cr GPIOA_CRL; shift pin * 4; // 每个引脚占4位 } else { cr GPIOA_CRH; shift (pin - 8) * 4; } // 清除原有配置 *cr ~(0xF shift); // 设置新配置 (MODE[1:0] CNF[1:0]) *cr | ((conf 2) | mode) shift; } // 设置引脚输出 void gpio_write(int pin, int value) { if (value) { GPIOA_BSRR 1 pin; // 置位寄存器 } else { GPIOA_BSRR 1 (pin 16); // 复位寄存器 } } // 读取引脚输入 int gpio_read(int pin) { return (GPIOA_IDR pin) 1; } // 翻转引脚 void gpio_toggle(int pin) { GPIOA_ODR ^ (1 pin); }4.2 通信协议编码场景描述曼彻斯特编码用于可靠数据传输。// 曼彻斯特编码每位用跳变表示0下降沿1上升沿 // 实际存储每位用2个bit表示10表示001表示1 // 编码函数 unsigned int manchester_encode(unsigned char data) { unsigned int encoded 0; for (int i 0; i 8; i) { // 取当前位 int bit (data (7 - i)) 1; if (bit 0) { encoded | (0b10 (i * 2)); // 10表示0 } else { encoded | (0b01 (i * 2)); // 01表示1 } } return encoded; // 返回16位编码 } // 解码函数 unsigned char manchester_decode(unsigned int encoded) { unsigned char data 0; for (int i 0; i 8; i) { // 提取每两位 int bits (encoded (i * 2)) 0x03; // 解码100, 011 if (bits 0b01) { data | (1 (7 - i)); } // 0b10表示0data相应位本来就是0 } return data; } // 检查编码错误 int manchester_check(unsigned int encoded) { for (int i 0; i 8; i) { int bits (encoded (i * 2)) 0x03; // 有效的曼彻斯特编码只能是01或10 if (bits ! 0b01 bits ! 0b10) { return 0; // 无效编码 } } return 1; // 有效 }5. 算法优化5.1 快速平方根倒数场景描述3D图形中频繁计算平方根倒数Quake III中的经典算法。float fast_inv_sqrt(float number) { long i; float x2, y; const float threehalfs 1.5F; x2 number * 0.5F; y number; // 关键步骤将浮点数当作整数处理 i *(long *)y; // 位级转换 i 0x5f3759df - (i 1); // 魔数操作 y *(float *)i; // 转换回浮点 // 牛顿迭代一次提高精度 y y * (threehalfs - (x2 * y * y)); return y; }5.2 位图索引数据库场景描述大型数据分析中使用位图索引加速查询。#define BITMAP_SIZE 1000000 #define WORDS_PER_BITMAP (BITMAP_SIZE / 32) // 位图索引结构 struct bitmap_index { unsigned int *bitmaps; // 每个值对应一个位图 int value_count; // 不同值的数量 int record_count; // 记录总数 }; // 创建位图索引 struct bitmap_index *create_bitmap_index(int value_count, int record_count) { struct bitmap_index *idx malloc(sizeof(struct bitmap_index)); idx-value_count value_count; idx-record_count record_count; // 为每个值分配位图 idx-bitmaps calloc(value_count * WORDS_PER_BITMAP, sizeof(unsigned int)); return idx; } // 插入记录 void insert_record(struct bitmap_index *idx, int record_id, int value) { int word_idx record_id / 32; int bit_idx record_id % 32; // 设置对应值的位图 idx-bitmaps[value * WORDS_PER_BITMAP word_idx] | (1 bit_idx); } // AND查询查找同时具有value1和value2的记录 void query_and(struct bitmap_index *idx, int value1, int value2, int *result, int *result_count) { *result_count 0; for (int w 0; w WORDS_PER_BITMAP; w) { // 对两个位图的对应字进行AND操作 unsigned int combined idx-bitmaps[value1 * WORDS_PER_BITMAP w] idx-bitmaps[value2 * WORDS_PER_BITMAP w]; // 提取所有为1的位 while (combined) { // 找到最低位的1 int bit __builtin_ctz(combined); // GCC内置函数计算尾随零 result[(*result_count)] w * 32 bit; // 清除最低位的1 combined combined - 1; } } } // OR查询查找具有value1或value2的记录 void query_or(struct bitmap_index *idx, int value1, int value2, int *result, int *result_count) { *result_count 0; for (int w 0; w WORDS_PER_BITMAP; w) { unsigned int combined idx-bitmaps[value1 * WORDS_PER_BITMAP w] | idx-bitmaps[value2 * WORDS_PER_BITMAP w]; while (combined) { int bit __builtin_ctz(combined); result[(*result_count)] w * 32 bit; combined combined - 1; } } } // 性能对比传统方法 vs 位图方法 // 传统SQLSELECT * FROM table WHERE colorred AND sizelarge // 需要全表扫描 O(n) // 位图索引位图AND操作 O(n/word_size)快32倍6. 游戏开发6.1 碰撞检测优化场景描述游戏中的碰撞检测需要快速筛选可能碰撞的物体。// 使用空间网格划分 #define GRID_SIZE 32 #define CELL_SIZE 64 struct game_object { float x, y; float vx, vy; int type; int collision_mask; }; // 网格单元位图 unsigned int grid[GRID_SIZE][GRID_SIZE][4]; // 每单元最多128个物体 // 计算物体所在网格 void update_grid_position(struct game_object *obj, int id) { int cell_x (int)(obj-x) / CELL_SIZE; int cell_y (int)(obj-y) / CELL_SIZE; // 限制在网格范围内 cell_x cell_x 0 ? 0 : (cell_x GRID_SIZE ? GRID_SIZE-1 : cell_x); cell_y cell_y 0 ? 0 : (cell_y GRID_SIZE ? GRID_SIZE-1 : cell_y); // 设置位图 int word_idx id / 32; int bit_idx id % 32; grid[cell_x][cell_y][word_idx] | (1 bit_idx); } // 检测碰撞 void check_collisions(struct game_object *obj, int id, int cell_x, int cell_y) { // 检查当前网格和相邻8个网格 for (int dx -1; dx 1; dx) { for (int dy -1; dy 1; dy) { int check_x cell_x dx; int check_y cell_y dy; if (check_x 0 || check_x GRID_SIZE || check_y 0 || check_y GRID_SIZE) { continue; } // 检查所有物体 for (int w 0; w 4; w) { unsigned int cell_objects grid[check_x][check_y][w]; // 快速跳过空字 if (cell_objects 0) continue; // 处理每个可能碰撞的物体 unsigned int remaining cell_objects; while (remaining) { int other_id w * 32 __builtin_ctz(remaining); // 不检查自己 if (other_id ! id) { // 检查碰撞掩码 if (obj-collision_mask other_collision_mask) { precise_collision_check(obj, objects[other_id]); } } // 清除已处理的位 remaining remaining - 1; } } } } }6.2 游戏状态压缩场景描述网络游戏需要压缩状态数据减少带宽。// 玩家状态原本需要多个字节 struct player_state { // 位置压缩到1212位 unsigned int x : 12; // 0-4095 unsigned int y : 12; // 0-4095 // 方向8位 unsigned int angle : 8; // 0-255对应0-360度 // 动画状态4位 unsigned int animation : 4; // 16种动画 // 标志位8个标志 unsigned int is_moving : 1; unsigned int is_jumping : 1; unsigned int is_crouching : 1; unsigned int is_attacking : 1; unsigned int is_hit : 1; unsigned int is_invincible : 1; unsigned int has_flag : 1; unsigned int is_visible : 1; // 血量7位 unsigned int health : 7; // 0-127 // 总共12128487 51位不到7字节 }; // 打包成网络包 void pack_player_state(struct player_state *state, unsigned char *buffer) { unsigned long long packed 0; int bitpos 0; // 逐个字段打包 packed | (unsigned long long)state-x bitpos; bitpos 12; packed | (unsigned long long)state-y bitpos; bitpos 12; packed | (unsigned long long)state-angle bitpos; bitpos 8; packed | (unsigned long long)state-animation bitpos; bitpos 4; // 打包8个标志位 unsigned char flags 0; flags | state-is_moving 0; flags | state-is_jumping 1; flags | state-is_crouching 2; flags | state-is_attacking 3; flags | state-is_hit 4; flags | state-is_invincible 5; flags | state-has_flag 6; flags | state-is_visible 7; packed | (unsigned long long)flags bitpos; bitpos 8; packed | (unsigned long long)state-health bitpos; bitpos 7; // 写入缓冲区7字节 for (int i 0; i 7; i) { buffer[i] (packed (i * 8)) 0xFF; } } // 解包 void unpack_player_state(unsigned char *buffer, struct player_state *state) { unsigned long long packed 0; // 从缓冲区读取 for (int i 0; i 7; i) { packed | (unsigned long long)buffer[i] (i * 8); } int bitpos 0; state-x (packed bitpos) 0xFFF; bitpos 12; state-y (packed bitpos) 0xFFF; bitpos 12; state-angle (packed bitpos) 0xFF; bitpos 8; state-animation (packed bitpos) 0xF; bitpos 4; unsigned char flags (packed bitpos) 0xFF; bitpos 8; state-is_moving (flags 0) 1; state-is_jumping (flags 1) 1; state-is_crouching (flags 2) 1; state-is_attacking (flags 3) 1; state-is_hit (flags 4) 1; state-is_invincible (flags 5) 1; state-has_flag (flags 6) 1; state-is_visible (flags 7) 1; state-health (packed bitpos) 0x7F; } // 对比传统结构需要20字节压缩后只需7字节7. 加密和安全7.1 简单流加密场景描述实时通信中的轻量级加密。struct stream_cipher { unsigned int state; // 内部状态 unsigned int key; // 密钥 unsigned char buffer[256]; // 密钥流缓冲区 int buf_pos; }; // 初始化 void cipher_init(struct stream_cipher *cipher, unsigned int key) { cipher-key key; cipher-state key; cipher-buf_pos 256; // 触发重新生成 // 初始扩散 for (int i 0; i 256; i) { cipher-state (cipher-state * 0x01000193) ^ (cipher-state 16); } } // 生成下一个密钥字节 unsigned char next_key_byte(struct stream_cipher *cipher) { // 线性反馈移位寄存器 (LFSR) unsigned int bit ((cipher-state 0) ^ (cipher-state 2) ^ (cipher-state 3) ^ (cipher-state 5)) 1; cipher-state (cipher-state 1) | (bit 31); // 与密钥混合 cipher-state ^ cipher-key; // 额外混淆 cipher-state (cipher-state 8) | ((cipher-state 24) 0xFF); return cipher-state 0xFF; } // 加密/解密同一个函数 void cipher_crypt(struct stream_cipher *cipher, unsigned char *data, int len) { for (int i 0; i len; i) { if (cipher-buf_pos 256) { // 重新填充缓冲区 for (int j 0; j 256; j) { cipher-buffer[j] next_key_byte