编程

一个有趣的编程技巧

学习笔记

Posted by BY CGH on May 7, 2026

前言

原本这篇帖子只是为了记录一个尤达表达式。没想到后面这些小技巧越堆越多，已经要改为“一些编程技巧”了。 这里需要注意的是，大部分这些技巧都是过时的或者不必要的，因为现代编译器已经替你完成了大部分工作，只不过了解一下还是很有启发性的

“尤达表达式”

这个出自星球大战的尤达，他喜欢倒装句。然后c语言中，很常见的一个错误就是使用类似’c==’/n’ ‘这种情况时，经常会忘记打多一个=导致被编译器解释为赋值c=’/n’，导致各种问题。因此有些老程序员有一种防御性编程技巧，即倒过来使用，’/n’==c,这样即使少打了个=，编译器会指出不能给常量赋值，因而避免了这类错误。

不用while(1)用for(;;)

这是因为早期内存/CPU紧张并且编译器不够智能的时候，while(1)中的1会被存进寄存器当成常量条件，每次循环都要判断一次很耗费CPU周期。 而for(;;)在任何编译器中都会被认为是空条件，单纯的死循环。这也是Zephyr或者各种底层库的常见操作。

工具宏

  • UTIL_CAT():

    Header Embedding（头部嵌入）/ Over-allocation with Metadata

    这是一种在 C 语言里”把元数据塞进数据本身”的技巧，核心思想是：在分配一块内存时，故意多分配一点空间，把描述这块内存的信息（长度、类型、引用计数、校验值、所属 owner 等）放在数据的前面，真正返回给调用者的指针指向元数据之后的位置。

基本布局

+--------------------------------------------------+
|  metadata (len / type / magic / refcount ...)    |  <- 真正 malloc 的起点
+--------------------------------------------------+
|  payload  (用户实际使用的数据)                    |  <- 返回给用户的指针
+--------------------------------------------------+

一个最小例子

#include <stdlib.h>
#include <string.h>
#include <stdint.h>

typedef struct {
    uint32_t magic;     // 魔数，用于校验
    uint32_t len;       // payload 长度
    uint32_t refcount;  // 引用计数
} BufMeta;

#define BUF_MAGIC 0xDEADBEEFu

/* 分配：多分配一个 header 的空间，返回 header 之后的地址 */
void *buf_alloc(size_t len) {
    BufMeta *meta = (BufMeta *)malloc(sizeof(BufMeta) + len);
    if (!meta) return NULL;
    meta->magic    = BUF_MAGIC;
    meta->len      = (uint32_t)len;
    meta->refcount = 1;
    return (uint8_t *)meta + sizeof(BufMeta);   /* 返回 payload 指针 */
}

/* 释放：从 payload 指针倒退回 header，做校验后再 free */
void buf_free(void *payload) {
    if (!payload) return;
    BufMeta *meta = (BufMeta *)((uint8_t *)payload - sizeof(BufMeta));
    if (meta->magic != BUF_MAGIC) {
        /* 这里可以 abort / log，防止 double-free 或野指针 */
        return;
    }
    meta->magic = 0;          /* 抹掉魔数，防止重复释放 */
    free(meta);
}

/* 反查：任何时候拿到 payload 都能拿到它的长度 */
uint32_t buf_len(const void *payload) {
    const BufMeta *meta = (const BufMeta *)((const uint8_t *)payload - sizeof(BufMeta));
    return meta->len;
}

为什么这么做

  1. 零额外开销的”自带描述”：不需要再维护一张 ptr -> 元数据 的哈希表，元数据跟着数据走，缓存局部性也好。
  2. 越界/双重释放检测：通过 magic 校验，能发现 free 了一个普通指针、或者重复 free 同一个 buffer。
  3. 隐藏实现细节：调用者只看到一个 void *，但库内部能反查出长度、类型、引用计数，实现类似”带类型的内存”。
  4. 对齐友好：只要 header 大小是 16/最大对齐的整数倍，payload 仍然满足对齐要求。

现实中的例子

  • Linux 内核 struct page / kmalloc：很多内核对象前面都带 header。
  • CPython 的 PyObject：每个对象前面都有一个 ob_refcnt + ob_type，这就是典型的 over-allocation with metadata。
  • glibc malloc 的 chunk header：malloc 返回的指针前面其实藏着 prev_size / size / flags，free 时靠它合并相邻块。
  • Objective-C / Swift 的对象头：isa 指针 + 引用计数都放在对象内存的最前面。
  • Zephyr / FreeRTOS 的内存池：每个 block 前面挂一个链表节点和长度字段。

和 0 长数组（柔性数组成员）的关系

0 长数组其实就是 over-allocation with metadata 的标准语法封装——它把”header + payload”这件事用结构体语法合法地表达出来，让你不用再手写指针倒退。

两种写法对比

手写倒退（本文前面的写法）：

BufMeta *meta = malloc(sizeof(BufMeta) + len);
void *payload = (uint8_t*)meta + sizeof(BufMeta);   /* 手动算偏移 */
/* 反查时要 payload - sizeof(BufMeta) */

0 长数组（C99 柔性数组成员）：

typedef struct {
    uint32_t magic;
    uint32_t len;
    uint32_t refcount;
    char data[];          /* 0 长数组，不占 sizeof */
} Buf;

Buf *b = malloc(sizeof(Buf) + len);   /* 一次分配 header + payload */
b->data[i];                           /* 直接访问，编译器帮你算偏移 */

关键区别

| 维度 | 手写指针倒退 | 0 长数组 | |——|————|———| | 内存布局 | header 紧贴 payload 前 | header 紧贴 payload 前（完全一样） | | 访问 payload | (uint8_t*)meta + sizeof(meta) | b->data，编译器代劳 | | 反查 header | payload - sizeof(meta) | 直接拿 b，不用倒退 | | 类型安全 | 全是 void* 强转 | 有类型，编译器检查 | | 对齐 | 要自己保证 header 是对齐整数倍 | 编译器自动保证 data[] 对齐 | | 谁用 | glibc malloc chunk、内核 slab | 应用层”变长结构体” |

本质是同一件事

两者底层内存布局完全相同：一块连续内存，前面是元数据，后面是变长数据。区别只是：

  • 0 长数组 = header 在前、payload 在后，通过结构体字段名访问，编译器帮你算 offsetof。
  • 手写倒退 = payload 在前（返回给用户）、header 在后（藏在前面），通过指针算术访问，因为对外暴露的接口是 void*，不想暴露 header 结构。

为什么 glibc / 内核用手写倒退，而不用 0 长数组

因为它们的对外接口是 void *malloc(size_t)——返回的就是 payload 指针，调用者根本不知道、也不该知道前面有 header。如果用 0 长数组，就得把 Buf* 暴露出去，破坏了 malloc 返回 void* 的通用契约。所以”藏 header”的场景必须手写倒退；而”自己内部用的变长结构体”用 0 长数组更干净。

为什么只适用于堆分配

这个技巧能成立，依赖一个前提：payload 指针往前退 sizeof(header) 字节，必须正好落在你自己分配的、合法的 header 上。

  • 堆：malloc(sizeof(header) + len) 返回的整块内存都是你的，header 紧贴 payload 前面，倒退一定命中 header。
  • 栈：char buf[100] 的地址就是数组本身，buf 前面是栈帧的其他内容——保存的帧指针、返回地址、其他局部变量。buf[-sizeof(header)] 访问的根本不是 header，而是栈帧里的关键数据，往那里写 magic 就是在破坏栈帧（这正是栈溢出攻击的原理）。

具体有三个原因：

  1. 栈大小编译期固定，无法”多分配”：over-allocation 的本质是运行时请求 header + payload，而 char buf[100] 写下来就是 100 字节，编译器不会多给你。
  2. 栈对象不能 free，”释放时倒退校验”没有用武之地：header 里的 magic / refcount 主要服务于 free 时的双重释放检测，栈对象出作用域自动回收，没有 free 这个动作。
  3. 栈指针的布局由编译器/ABI 决定，不由你：堆是你 malloc 的，你确定前面有 header；栈数组是编译器摆的，前面挨着什么你不知道。

变通方法（但那已经不是 over-allocation）：如果确实想在栈上用”带 header 的对象”，可以显式声明结构体：

struct {
    BufMeta meta;
    char payload[100];
} s;

这样 &s.payload 前面确实有 header，可以反查长度。但这叫显式组合，不是 over-allocation——你没有”多分配”，只是把两个字段拼在一起，而且仍然不能 free。

注意事项

  • 释放必须配对：用 buf_alloc 分配的，必须用 buf_free 释放，不能直接丢给 free，否则 header 会被当成 payload 的一部分，导致 free 错位。
  • 指针算术要小心对齐：payload - sizeof(BufMeta) 必须落在合法的 header 起点上，所以 header 大小最好是对齐的整数倍。
  • 只适用于堆分配：详见上一节，栈数组前面没有属于你的 header，强行倒退会破坏栈帧。
  • 多线程下 refcount 要用原子操作：__atomic / stdatomic.h，否则会有数据竞争。

异或小技巧

异或是个很有趣的运算： 30^40^40=30,也就是a^b^b=a 这有什么用呢？这说明你可以对字符串进行莫名其妙的修改，也就是对其进行异或变成你看不懂的东西 然后你如果再异或一遍，这个玩意就会自己变回来，很神奇吧？ 这是一种加密手段，虽然不算特别安全，但是也很方便实用。 另外一种小技巧是用于交换变量，假设我们要交换a和b a=114,b=514
a^b=114^514
由于异或运算和顺序无关，所以你可以：
b^=a=114^514^514=a^b^b=a^b^b=114; 此时b=a（114）。
然后a=114^514
a^b=114^514^114=514;
此时a=b（514）
很神奇吧？ 虽然编译器会帮我们解决这个问题，但是它依然是个很有趣的编程技巧。
还有一种用法是寻找重复数，这当然也和之前的原理一样：异或多次会留下其本身 这里就引用ai的话，不赘述了，这是个很常见也很无聊的面试技巧： 假设标准范围是 1, 2, 3, 4, 5。我们把 “标准范围” 和 “实际数组” 的所有数字，全部扔进同一个异或大锅里。

🔹 场景 A：找缺失的数

实际数组：1, 2, 4, 5 （缺了 3）
大锅里煮：1^2^3^4^5 (标准) ^ 1^2^4^5 (实际)
消消乐过程：1和1抵消，2和2抵消，4和4抵消，5和5抵消。
最终结果：只剩下 3。（因为3只在标准里出现了一次，没被抵消掉）
🔹 场景 B：找重复的数

实际数组：1, 2, 3, 3, 4, 5 （3 重复了）
大锅里煮：1^2^3^4^5 (标准) ^ 1^2^3^3^4^5 (实际)
消消乐过程：1,2,4,5 都出现了两次，全部抵消。
重点看 3：标准里有1个3，实际里有2个3，一共3个3。
3 ^ 3 ^ 3 = (3 ^ 3) ^ 3 = 0 ^ 3 = 3。
最终结果：还是剩下 3。 当然这个只能用来查找单个的缺失/重复，原因很简单，有别的数的重复或者更多次的重复，这个式子的a^b^b就被破坏了。 当然还有更进阶的技巧,比如异或链表。

以下是关于异或链表（XOR Linked List） 的专业技术笔记。

一、 核心概念

异或链表是一种内存优化的双向链表变体。它利用按位异或（XOR）运算的自反性，将传统双向链表中的 prev（前驱）和 next（后继）两个指针域合并为一个 npx（Next/Previous XOR）指针域，从而将每个节点的指针内存开销降低 50%。

二、 运算原理

设节点 $B$ 的前驱地址为 $A$，后继地址为 $C$。

  • 存储规则：B.npx = A ^ C
  • 推导后继：已知前驱 $A$，则 C = B.npx ^ A
  • 推导前驱：已知后继 $C$，则 A = B.npx ^ C

三、 代码示例 (C语言)

在 C 语言中，需使用 uintptr_t 类型来安全地进行指针的整数转换与异或运算。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

// 1. 节点定义
struct Node {
    int data;
    uintptr_t npx; // 存储 prev ^ next 的异或值
};

// 2. 异或辅助函数
uintptr_t XOR(uintptr_t a, uintptr_t b) {
    return a ^ b;
}

// 3. 获取下一个节点（必须已知前一个节点）
struct Node* get_next(struct Node* prev, struct Node* curr) {
    return (struct Node*)(curr->npx ^ (uintptr_t)prev);
}

// 4. 正向遍历异或链表
void traverse_forward(struct Node* head) {
    struct Node* curr = head;
    struct Node* prev = NULL;
    struct Node* next;

    while (curr != NULL) {
        printf("%d ", curr->data);
        
        // 计算下一个节点地址
        next = get_next(prev, curr);
        
        // 指针向后移动
        prev = curr;
        curr = next;
    }
    printf("\n");
}

// 5. 在头部插入节点
void insert_at_head(struct Node** head_ref, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    
    // 新节点的前驱为 NULL，后继为当前头节点
    new_node->npx = (uintptr_t)NULL ^ (uintptr_t)(*head_ref);

    // 如果链表非空，更新原头节点的 npx
    if (*head_ref != NULL) {
        // 原头节点的前驱变为新节点，后继不变
        // 原 npx = NULL ^ next，新 npx = new_node ^ next
        (*head_ref)->npx = (uintptr_t)new_node ^ ((uintptr_t)NULL ^ (*head_ref)->npx);
    }

    *head_ref = new_node;
}

异或链表是“以计算换空间”的典型数据结构。它适用于内存极度受限且对调试要求不高的底层嵌入式场景；在现代通用软件开发中，因维护成本和调试成本过高，通常不作为首选方案，更多作为考察位运算与指针操作深度的算法考点。

FOOTGUN

“footgun”是一个俚语，尤其在编程中，指的是看似有用但极易被滥用的特性或设计，导致自我造成的错误或问题，比如用设计不良的武器意外射中自己的脚。

CATALOG
    FEATURED TAGS
    iOS 开发技巧 Debug Obj-C Xcode ReactiveCocoa 函数式编程 开源框架 Runtime 生活 Blog Mac 效率 终端 Git Swift CocoaPods zsh 开源库 ruby shell 健身 日常 感想 编程 嵌入式
    FRIENDS