Lesson 15: 统计二进制 1 的个数 CNB

练习任务

本课包含三个递进练习，从基础到高级，逐步掌握位运算的精髓：

练习 1（逐位检测）：实现 count_bits(num)，用 for 循环 32 次，每次用 num & (1 << i) 检查第 i 位是否为 1，累计计数器。

练习 2（n & (n-1) 清最低位）：实现 count_bits(num)，用 while (num != 0) { num &= (num - 1); sum++; } 技巧——每次循环清除最右边的一个 1，循环次数等于 1 的个数。

练习 3（popcount 分治法）：用 5 层掩码-移位-加法实现 O(1) 的 popcount：M1=0x55555555（每 2 位一组）、M2=0x33333333（每 4 位一组）、M3=0x0F0F0F0F（每 8 位一组）、M4=0x00FF00FF（每 16 位一组）、M5=0x0000FFFF（高 16 位+低 16 位）。每层做 sum = (sum & Mk) + ((sum >> k) & Mk)。

提示：这三种算法的时间复杂度各不相同——第一种固定循环 32 次，第二种只循环"1 的个数"次，第三种只需 5 步。思考一下：为什么 n & (n-1) 恰好清除最右边的 1？popcount 分治法的并行加法又是怎么做到的？

核心知识点

位运算 & — 按位与：1 & 1 == 1，1 & 0 == 0，0 & 0 == 0
位运算 | — 按位或：1 | 0 == 1，0 | 0 == 0，1 | 1 == 1
位运算 ~ — 按位取反：~0x1F == 0xFFFFFFE0
位运算 ^ — 按位异或：1 ^ 1 == 0，1 ^ 0 == 1（相同为 0，不同为 1）
移位 << >> — 左移等价于乘 2，右移等价于除 2（无符号数）
掩码构造 — 1 << i 生成只有第 i 位为 1 的掩码
逐位检测算法 — for (i = 0; i < 32; i++) if (num & (1 << i)) counter++
n & (n-1) 清最低位 — 每次循环消除最右边的 1，循环次数等于 1 的个数
popcount 分治法 — 5 层掩码 + 移位 + 加法，O(1) 时间内并行统计
SWAR (SIMD Within A Register) — 在一个寄存器内并行处理多个数据的思想
位域 bit-field — unsigned int is_keyword : 1 以位为单位声明结构体成员
位域与大端小端 — TCP 头中位域布局依赖字节序（回顾 Lesson 12）
位操作优先级陷阱 — & | ^ 优先级低于 == != < >
set_bit / get_bit — 用位运算设置和读取特定位
大小写转换 — 异或 0x20 翻转 ASCII 第 5 位（'A' ^ 0x20 == 'a'）
位运算打印进制 — 逐位提取实现 print_bin / print_oct / print_hex

代码框架

练习 1：逐位检测

15a_count_bits_loop.c

#include <stdio.h>

int count_bits(int num)
{
    int sum = 0;
    int i;
    // 在这里实现：for (i = 0; i < 32; i++)
    //              if (num & (1 << i)) sum++;
    return sum;
}

int main(void)
{
    int num;
    scanf("%d", &num);
    printf("%d\n", count_bits(num));
    return 0;
}

练习 2：n & (n-1) 清最低位

15b_count_bits_clear.c

#include <stdio.h>

int count_bits(int num)
{
    int sum = 0;
    // 在这里实现：while (num != 0) { num &= (num - 1); sum++; }
    return sum;
}

int main(void)
{
    int num;
    scanf("%d", &num);
    printf("%d\n", count_bits(num));
    return 0;
}

练习 3：popcount 分治法

bits.c

#include <stdio.h>

#define M1  0x55555555   // 0101 0101 0101 0101 0101 0101 0101 0101
#define M2  0x33333333   // 0011 0011 0011 0011 0011 0011 0011 0011
#define M3  0x0F0F0F0F   // 0000 1111 0000 1111 0000 1111 0000 1111
#define M4  0x00FF00FF   // 0000 0000 1111 1111 0000 0000 1111 1111
#define M5  0x0000FFFF   // 0000 0000 0000 0000 1111 1111 1111 1111

int count_bits(int num)
{
    int sum = num;
    // 在这里实现 5 层分治：
    // 第 1 层：sum = (sum & M1) + ((sum >>  1) & M1);
    // 第 2 层：sum = (sum & M2) + ((sum >>  2) & M2);
    // 第 3 层：sum = (sum & M3) + ((sum >>  4) & M3);
    // 第 4 层：sum = (sum & M4) + ((sum >>  8) & M4);
    // 第 5 层：sum = (sum & M5) + ((sum >> 16) & M5);
    return sum;
}

int main(void)
{
    int num;
    scanf("%d", &num);
    printf("%d\n", count_bits(num));
    return 0;
}

填充框架时的关键思考：练习 1 中为什么循环 32 次而不是 31 次？练习 2 中 n &= (n-1) 为什么恰好清除最右边的 1？练习 3 中每层掩码的二进制模式有什么规律？

TIP

先不要往下翻看参考解答。建议按顺序完成三道练习——练习 1 建立位运算基本功，练习 2 感受算法优化的巧妙，练习 3 理解分治法思想。每道题都可用 15 和 1024 两个测试用例验证。

深度讲解

1. 位运算基础：C 语言的二进制操作

1.1 六种位运算符一览

C 语言提供了 6 种位运算符，它们直接在整数的二进制表示上操作：

运算符	名称	规则	示例 (a=0b1100, b=0b1010)
`&`	按位与	两位都为 1 才为 1	`a & b = 0b1000`
`\|`	按位或	至少一位为 1 就为 1	`a \| b = 0b1110`
`^`	按位异或	两位不同才为 1	`a ^ b = 0b0110`
`~`	按位取反	0 变 1，1 变 0	`~a = 0b...0011`
`<<`	左移	左移 n 位，右边补 0	`a << 1 = 0b11000`
`>>`	右移	右移 n 位，左边补什么取决于符号	`a >> 1 = 0b0110`

关键区分：位运算符 & | 和逻辑运算符 && || 是完全不同的概念！

bit_vs_logic.c

#include <stdio.h>

int main(void)
{
    // 位运算：按位操作
    printf("1 & 2 = %d\n", 1 & 2);    // 0b01 & 0b10 = 0b00 = 0
    printf("1 | 2 = %d\n", 1 | 2);    // 0b01 | 0b10 = 0b11 = 3

    // 逻辑运算：整体判断
    printf("1 && 2 = %d\n", 1 && 2);  // 两个都非 0 → true = 1
    printf("1 || 2 = %d\n", 1 || 2);  // 有一个非 0 → true = 1

    // 更多示例
    printf("5 & 10 = %d\n", 5 & 10);  // 0b0101 & 0b1010 = 0b0000 = 0
    printf("5 && 10 = %d\n", 5 && 10);// 两个都非 0 → true = 1

    return 0;
}

CAUTION

把 & 误写为 && 是 C 语言中最隐蔽的 bug 之一——前者按位与，后者逻辑与。if (status & 0x4000) 和 if (status && 0x4000) 的含义截然不同：前者判断 status 的第 14 位是否为 1，后者判断 status 和 0x4000 是否都非零（后者几乎总是为真）。

1.2 常见位操作模式

bit_operations.c

#include <stdio.h>

int main(void)
{
    int a = 0x00;  // 0000 0000

    // 1. 设置某位 (set bit): a |= 1 << pos
    a |= 1 << 4;                    // 设置第 4 位 → 0001 0000 = 0x10
    printf("set bit 4:   0x%02x\n", a);

    // 2. 清除某位 (clear bit): a &= ~(1 << pos)
    a &= ~(1 << 4);                 // 清除第 4 位 → 0000 0000 = 0x00
    printf("clear bit 4: 0x%02x\n", a);

    // 3. 测试某位 (test bit): a & (1 << pos)
    a = 0x80;                       // 1000 0000
    if (a & (1 << 7))               // 测试第 7 位
        printf("bit 7 is set\n");

    // 4. 翻转某位 (toggle bit): a ^= 1 << pos
    a ^= 1 << 0;                    // 翻转第 0 位
    printf("toggle bit 0: 0x%02x\n", a);

    // 5. 取反构造数
    printf("~0x00 = 0x%08x\n", ~0x00);   // 全 1: 0xFFFFFFFF
    printf("~0x1F = 0x%08x\n", ~0x1F);   // 0xFFFFFFE0

    // 6. 设置位域 (set bit-field)
    a = 0x0000;
    a &= ~(0x7 << 28);              // 先清除 bit28-bit30
    a |= 0x5 << 28;                 // 再设置为 101

    // 7. 获取位域 (get bit-field)
    int field = (a >> 28) & 0x7;    // 提取 bit28-bit30
    printf("field = 0x%x\n", field);

    return 0;
}

这 7 种操作模式是嵌入式开发、驱动编程、协议解析中的基本功。理解它们不需要死记硬背——关键是理解 1 << pos 生成一个"只在第 pos 位为 1 的掩码"，然后 &、|、~ 分别执行"筛选"、"置位"、"取反"功能。

1.3 位运算优先级的致命陷阱

precedence_trap.c

#include <stdio.h>

int main(void)
{
    int status = 0;

    // 陷阱：& 的优先级低于 ==
    if (status & 0x4000 == 0)       // 等价于 status & (0x4000 == 0)
        printf("this might not do what you think!\n");

    // 正确写法：加括号
    if ((status & 0x4000) == 0)     // 先做位与，再判等
        printf("bit 14 is clear\n");

    // 优先级顺序 (从高到低):
    // ~ > << >> > & > ^ > | > == != > && > ||
    // 取反 > 移位 > 与 > 异或 > 或 > 判等 > 逻辑与 > 逻辑或

    return 0;
}

WARNING

位运算符 & ^ | 的优先级低于关系运算符 == != < >。因此 (a & mask == 0) 被解析为 (a & (mask == 0))——这几乎肯定不是你的本意。永远在混合位运算和比较运算时加括号。

2. 逐位检测算法：位运算的直观入门

2.1 算法原理

bit_by_bit.c

int count_bits(int num)
{
    int sum = 0;
    for (int i = 0; i < 32; i++)      // int 有 32 位
        if (num & (1 << i))            // 检查第 i 位是否为 1
            sum++;
    return sum;
}

核心思路：用一个"探针" 1 << i 依次指向每一位，用 & 运算检查该位是否为 1。

以 num = 15 (0x0F, 二进制 0000...0000 1111) 为例：

i=0:  1 << 0 = 0000...0000 0001    num & mask = 0001 → 非 0 ✓ sum=1
i=1:  1 << 1 = 0000...0000 0010    num & mask = 0010 → 非 0 ✓ sum=2
i=2:  1 << 2 = 0000...0000 0100    num & mask = 0100 → 非 0 ✓ sum=3
i=3:  1 << 3 = 0000...0000 1000    num & mask = 1000 → 非 0 ✓ sum=4
i=4:  1 << 4 = 0000...0001 0000    num & mask = 0000 → 0   ✗ sum=4
...
i=31: 1<<31 = 1000...0000 0000    num & mask = 0000 → 0   ✗ sum=4

结果: 4 个 1

2.2 为什么循环 32 次？

sizeof_int.c

#include <stdio.h>

int main(void)
{
    printf("sizeof(int) = %zu bytes\n", sizeof(int));
    printf("bits in int  = %zu\n", sizeof(int) * 8);
    // 通常 int 为 4 字节 = 32 位
    return 0;
}

sizeof(int) 通常为 4（字节），即 32 位。循环上界 sizeof(int) * 8 比写死 32 更具可移植性——虽然绝大多数平台 int 是 32 位，但用 sizeof(int) * 8 确保代码在 int 为其他大小的平台上也能正确工作。

portable_count.c

int count_bits(int num)
{
    unsigned int i;
    int counter = 0;

    for (i = 0; i < sizeof(int) * 8; i++)   // 用 sizeof 保证可移植
        if ((num >> i) & 0x01)
            counter++;

    return counter;
}

注意这里用 (num >> i) & 0x01 替代 num & (1 << i)——两种写法等价。前者把待检测位移到第 0 位再用 0x01 测试，后者用移动的掩码去测试原位。

2.3 循环次数分析

逐位检测算法的时间复杂度：固定 O(32) = O(1)——无论 num 中有多少个 1，总是循环 32 次。

num = 1024 (0x400)  → 只有 1 个 1，但仍然循环 32 次
num = -1 (0xFFFFFFFF) → 有 32 个 1，也是循环 32 次

这是最简单的算法，也是位运算最好的入门练习——它让你直观理解"掩码"和"移位"这两个核心概念。

3. n & (n-1)：一个魔法般的位运算技巧

3.1 算法原理

clear_lowest.c

int count_bits(int num)
{
    int counter = 0;
    while (num != 0)          // 当 num 中还有 1 时继续
    {
        num &= (num - 1);     // 清除最右边的 1
        counter++;
    }
    return counter;
}

n & (n-1) 的魔法：它恰好清除 n 的二进制表示中最右边的一个 1。

手动追踪 n = 15 (0b1111) 的执行过程:

第 1 次循环:
  n     = 1111 (15)
  n-1   = 1110 (14)
  n&(n-1) = 1110 (14)    ← 最右边的 1 被清掉了！ counter=1

第 2 次循环:
  n     = 1110 (14)
  n-1   = 1101 (13)
  n&(n-1) = 1100 (12)    ← 又清掉一个 1       counter=2

第 3 次循环:
  n     = 1100 (12)
  n-1   = 1011 (11)
  n&(n-1) = 1000 (8)     ← 又清掉一个 1       counter=3

第 4 次循环:
  n     = 1000 (8)
  n-1   = 0111 (7)
  n&(n-1) = 0000 (0)     ← 最后一个 1 也被清掉 counter=4

n == 0 → 退出循环，返回 4

3.2 为什么 n & (n-1) 恰好清除最右边的 1？

这是二进制的借位减法在起作用：

考虑任意二进制数 n，设其最右边的 1 在位置 k:

n     = ...1 0 0 ... 0 0    ← 第 k 位是 1，右边全是 0
           ↑
          位置 k

n-1   = ...0 1 1 ... 1 1    ← 借位: 第 k 位变成 0，右边全变成 1

n&(n-1):
  ...1 0 0 ... 0 0    (n)
& ...0 1 1 ... 1 1    (n-1)
──────────────────
  ...0 0 0 ... 0 0    ← 第 k 位及右边全变成 0，左边不变！

减法 n-1 从位置 k 借走一个 1，导致：

位置 k 从 1 变 0
位置 k 右边的所有 0 变 1
位置 k 左边的所有位不变

因此 n & (n-1) 保留了左边的位，清除了第 k 位及其右边的所有位——恰好清除了最右边的 1。

3.3 不同输入的行为对比

compare_n_and_nminus1.c

#include <stdio.h>

void show_clear(int n)
{
    printf("n     = 0x%08x  (binary: ", n);
    for (int i = 31; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf(")\n");

    printf("n-1   = 0x%08x\n", n - 1);
    printf("n&(n-1) = 0x%08x  ← 清掉了最右边的 1\n\n", n & (n - 1));
}

int main(void)
{
    show_clear(0x64);   // 0110 0100 → 0110 0000
    show_clear(0x0F);   // 0000 1111 → 0000 1110
    show_clear(0x8000); // 1000...0000 → 0 (唯一的 1 被清掉)
    return 0;
}

输出：

n     = 0x00000064  (binary: 00000000000000000000000001100100)
n-1   = 0x00000063
n&(n-1) = 0x00000060  ← 清掉了最右边的 1

n     = 0x0000000f  (binary: 00000000000000000000000000001111)
n-1   = 0x0000000e
n&(n-1) = 0x0000000e  ← 清掉了最右边的 1

n     = 0x00008000  (binary: 00000000000000001000000000000000)
n-1   = 0x00007fff
n&(n-1) = 0x00000000  ← 唯一的 1 被清掉，结果为 0

3.4 算法优势分析

对比维度	逐位检测	n & (n-1)
循环次数	固定 32 次	等于 1 的个数
最佳情况	32 次 (num=0 也 32 次)	0 次 (num=0 直接跳过)
最差情况	32 次	32 次 (num=-1, 全是 1)
平均情况	32 次	16 次 (平均一半的位是 1)
代码行数	~5 行	~5 行
可读性	直观易懂	需要理解 n&(n-1) 原理

n & (n-1) 的优势在于循环次数等于 1 的个数——对于"稀疏"的数（1 很少），效率显著高于逐位检测。例如 1024 (0x400) 只有一个 1，逐位检测循环 32 次，而 n & (n-1) 只需循环 1 次。

3.5 n & (n-1) 的其他妙用

这个技巧不仅仅用于统计 bit 1 的个数：

n_and_nminus1_applications.c

#include <stdio.h>

int main(void)
{
    int n;

    // 1. 判断一个数是否为 2 的幂
    //    2 的幂的二进制形式：只有 1 个 1
    //    例如 1(0001), 2(0010), 4(0100), 8(1000)...
    n = 64;
    if (n > 0 && (n & (n - 1)) == 0)
        printf("%d is a power of 2\n", n);    // 64 = 2^6 ✓

    n = 100;
    if (n > 0 && (n & (n - 1)) == 0)
        printf("%d is a power of 2\n", n);    // 不输出 ✗
    // 100 = 0b1100100, n&(n-1) = 0b1100000 ≠ 0

    // 2. 计算一个数二进制末尾有多少个 0 (trailing zeros)
    n = 0x60;  // 0110 0000, 末尾 5 个 0
    int tz = 0;
    while ((n & 1) == 0) {
        tz++;
        n >>= 1;
    }
    printf("trailing zeros: %d\n", tz);   // 5

    // 3. 用 n&(n-1) 生成所有子集（组合数学中的经典技巧）
    int mask = 0x0F;  // 0b1111
    printf("subsets of 0x0F: ");
    for (int sub = mask; sub; sub = (sub - 1) & mask)
        printf("0x%02x ", sub);
    printf("\n");
    // 输出: 0x0f 0x0e 0x0d 0x0c 0x0b 0x0a 0x09 0x08
    //       0x07 0x06 0x05 0x04 0x03 0x02 0x01

    return 0;
}

n & (n-1) 是位运算中最常用的技巧之一——它出现在 2 的幂判断、子集枚举、汉明距离计算等众多场景中。

4. popcount 分治法：5 步完成 O(1) 统计

4.1 从逐位求和到并行加法

前两种算法都是逐位处理——要么逐位检测，要么逐位清除。有没有办法一次性处理所有位？

思路转变:
  逐位检测:   检查第 0 位 → 检查第 1 位 → ... → 检查第 31 位
                (串行，32 步)

  分治法:     把 32 位分成 16 组，每组 2 位 → 同时处理 16 组
               把结果合并成 8 组，每组 4 位 → 同时处理 8 组
               把结果合并成 4 组，每组 8 位 → 同时处理 4 组
               ...
               (并行，5 步)

这就是 popcount 分治法的核心思想——SWAR (SIMD Within A Register)：在一个 32 位寄存器内并行处理多个数据。

4.2 第 1 层：每 2 位一组

popcount_layer1.c

#include <stdio.h>

int main(void)
{
    unsigned int x = 0x6D;   // 0110 1101 (有 5 个 1)

    // 第 1 层掩码：0x55555555 = 0101 0101 0101 ... 0101
    // 保留每个 2 位组中的低 1 位（偶数位）
    unsigned int m1 = 0x55555555;

    // x & m1:        保留每个 2 位组的低 1 位
    // (x >> 1) & m1: 把每个 2 位组的高 1 位移到低 1 位，再保留
    // 两者相加 = 每 2 位组中 1 的个数
    x = (x & m1) + ((x >> 1) & m1);

    printf("after layer 1: x = 0x%08x\n", x);
    // 以 0x6D 为例:
    //   原始: 01 10 11 01 (每 2 位一组)
    //   分组统计: 01(1个1) 01(1个1) 10(2个1) 01(1个1)
    //   结果:   01 01 10 01 = 0x59

    return 0;
}

第 1 层图解（以 0x6D = 0110 1101 为例）:

原始数据:
  ┌────┬────┬────┬────┐
  │ 01 │ 10 │ 11 │ 01 │  每 2 位一组，共 4 组（简化为 8 位演示）
  └────┴────┴────┴────┘

x & 0x55 (0101 0101):
  ┌────┬────┬────┬────┐
  │ 01 │ 00 │ 01 │ 01 │  只保留每组的低位
  └────┴────┴────┴────┘

(x >> 1) & 0x55:
  先右移 1 位:  ┌────┬────┬────┬────┐
                │ 00 │ 11 │ 01 │ 10 │
                └────┴────┴────┴────┘
  再 & 0x55:    ┌────┬────┬────┬────┐
                │ 00 │ 01 │ 01 │ 00 │  原来每组的最高位移到了低位
                └────┴────┴────┴────┘

相加:
  ┌────┬────┬────┬────┐
  │ 01 │ 01 │ 10 │ 01 │  = 每组的 1 的个数！
  └────┴────┴────┴────┘
    1    1    2    1   ← 每组 2 位中分别有 1,1,2,1 个 1

4.3 完整 5 层分治

popcount_full.c

#include <stdio.h>

int count_bits(unsigned int x)
{
    // 掩码定义
    const unsigned int m1  = 0x55555555;  // 0101 0101 ...
    const unsigned int m2  = 0x33333333;  // 0011 0011 ...
    const unsigned int m4  = 0x0F0F0F0F;  // 0000 1111 ...
    const unsigned int m8  = 0x00FF00FF;  // 0000 0000 1111 1111 ...
    const unsigned int m16 = 0x0000FFFF;  // 0000 0000 0000 0000 1111 1111 1111 1111

    // 第 1 层：每 2 位 → 1 的个数存入那 2 位 (值域 0~2)
    x = (x & m1) + ((x >>  1) & m1);

    // 第 2 层：每 4 位 → 前两个 2 位组的和存入那 4 位 (值域 0~4)
    x = (x & m2) + ((x >>  2) & m2);

    // 第 3 层：每 8 位 → 前两个 4 位组的和存入那 8 位 (值域 0~8)
    x = (x & m4) + ((x >>  4) & m4);

    // 第 4 层：每 16 位 → 前两个 8 位组的和存入那 16 位 (值域 0~16)
    x = (x & m8) + ((x >>  8) & m8);

    // 第 5 层：整个 32 位 → 高 16 位 + 低 16 位 (值域 0~32)
    x = (x & m16) + ((x >> 16) & m16);

    return x;
}

int main(void)
{
    printf("count_bits(0x6D) = %d\n", count_bits(0x6D));     // 5
    printf("count_bits(0xFFFFFFFF) = %d\n", count_bits(0xFFFFFFFF)); // 32
    printf("count_bits(0) = %d\n", count_bits(0));           // 0
    return 0;
}

4.4 完整追踪示例

以 x = 0x3A6D (二进制: 0011 1010 0110 1101) 为例，逐步追踪每层变换：

第 1 层 (k=1, 掩码 0x55555555):
  原始:     00 11 10 10 01 10 11 01 (每 2 位一组的原始数据)
  组内 1 个数: 0  2  1  1  1  1  2  1
  结果:     00 10 01 01 01 01 10 01 = 0x251559

第 2 层 (k=2, 掩码 0x33333333):
  输入:     0000 0010 0001 0101 0001 0101 1001 0001 (每 2 位一组，值代表 1 的个数)
  重新分组为每 4 位:
            00+10=2  01+01=2  01+01=2  10+01=3
  结果:     0010 0010 0010 0011 = 0x2223

第 3 层 (k=4, 掩码 0x0F0F0F0F):
  输入:     0000 0010 0010 0010 0010 0011 ... (每 4 位一组)
  重新分组为每 8 位:
            0010+0010=4  0010+0011=5
  结果:     00000100 00000101 = 0x0405

第 4 层 (k=8, 掩码 0x00FF00FF):
  输入:     00000000 00000100 00000000 00000101
  重新分组为每 16 位:
            00000100+00000101=9
  结果:     00000000 00001001 = 0x0009

第 5 层 (k=16, 掩码 0x0000FFFF):
  输入:     00000000 00000000 00000000 00001001
  高 16 + 低 16:
            0 + 9 = 9
  结果:     9 ← 最终答案！

验证: 0x3A6D = 0011 1010 0110 1101
  数一数: 0+0+1+1 + 1+0+1+0 + 0+1+1+0 + 1+1+0+1
         = 2 + 2 + 2 + 3 = 9 ✓

4.5 掩码的规律

观察 5 个掩码的二进制模式，你会发现一个优美的规律：

M1  = 0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
                    └─┬─┘ └─┬─┘
                     每 2 位: 01 重复

M2  = 0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
                    └──┬──┘ └──┬──┘
                     每 4 位: 0011 重复

M4  = 0x0F0F0F0F = 0000 1111 0000 1111 0000 1111 0000 1111
                    └───┬───┘ └───┬───┘
                     每 8 位: 00001111 重复

M8  = 0x00FF00FF = 00000000 11111111 00000000 11111111
                    └────┬────┘ └────┬────┘
                     每 16 位: 0000000011111111 重复

M16 = 0x0000FFFF = 0000000000000000 1111111111111111
                    └──────┬──────┘ └──────┬──────┘
                     每 32 位: 低 16 位全 1

规律：第 k 层的掩码 = 每 2k 位中，低 k 位为 1，高 k 位为 0，重复填满 32 位。这个模式使得 x & Mk 恰好提取出每个分组的"低位部分"，而 (x >> k) & Mk 恰好提取出"高位部分"——两者相加完成了该层分组的归并。

4.6 为什么需要 & 掩码？

一个常见的疑问：为什么第 1 层不能直接写 x = (x & m1) + (x >> 1)？

why_mask.c

#include <stdio.h>

int main(void)
{
    unsigned int x = 0xFFFFFFFF;

    // 错误写法：不加掩码
    unsigned int bad = (x & 0x55555555) + (x >> 1);
    printf("without mask on shifted part: 0x%08x\n", bad);
    // 高位会"污染"低位的计算结果！

    // 正确写法：移位后也加掩码
    unsigned int good = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    printf("with mask on shifted part:    0x%08x\n", good);

    return 0;
}

原因：x >> 1 后，每个 2 位组的高位（原始数据的低位）移到了当前组的低位，但如果不加掩码，相邻组的高位也会泄漏过来。& m1 的作用就是屏蔽这些"跨组泄漏"的位，保证每组计算独立。

NOTE

最后一层 m16 的掩码在某些实现中可以省略——因为 32 位整数中高 16 位和低 16 位各自的值域最多为 16，相加最多为 32，不会溢出到高位。但保留掩码使代码更统一、更安全。

4.7 时间复杂度分析

算法	循环次数	操作数	适用场景
逐位检测	32 次	~64 条指令	教学入门
n & (n-1)	1~32 次	平均 ~32 条指令	稀疏数据（1 较少）
popcount 分治	0 次循环	固定 10 条位运算	高性能场景、编译器内置

popcount 分治法的操作次数完全独立于输入——无论是 0 还是 0xFFFFFFFF，总是 5 层掩码-移位-加法。这就是 gcc __builtin_popcount() 和大多数现代 CPU 的 POPCNT 指令的底层原理。

5. 位域 bit-field：以位为单位的数据结构

5.1 位域的基本语法

bitfield_basic.c

#include <stdio.h>

struct flag
{
    unsigned int is_keyword  : 1;   // 占 1 位
    unsigned int is_extern   : 1;   // 占 1 位
    unsigned int is_static   : 1;   // 占 1 位
    unsigned int is_mid      : 4;   // 占 4 位 (值域 0~15)
    unsigned int is_high     : 1;   // 占 1 位
    unsigned int is_highest  : 30;  // 占 30 位
} flags;

int main(void)
{
    flags.is_keyword = 1;
    flags.is_extern  = 1;
    flags.is_high    = 1;
    flags.is_mid     = 2;

    printf("flags = 0x%x\n", *(unsigned int*)&flags);
    printf("sizeof(flags) = %zu\n", sizeof(flags));
    // 总位数: 1+1+1+4+1+30 = 38 位 → 至少需要 8 字节 (64 位)

    return 0;
}

位域的本质：让结构体成员以**位（bit）**为单位占用存储空间，而不是以字节为单位。语法 类型成员名 : 宽度 中，宽度指定该成员占用的位数。

5.2 位域的内存布局

flags 的内存布局（示意，实际布局依赖编译器和大端小端）:

  bit:  63 ... 34 | 33 | 32-29 | 28 | 27 | 26 | 25-0
        ──────────┼────┼───────┼────┼────┼────┼────────
        未使用     │high│is_mid │stat│ext │key │is_highest
        或填充     │ :1 │  :4   │:1  │:1  │:1  │  :30

位域的大小遵循以下规则：

sizeof(flags) 向上取整到 unsigned int 的整数倍
如果成员总位数超过一个 unsigned int 的容量，会分配多个 unsigned int
跨字边界时编译器可能插入填充位（padding）

bitfield_sizeof.c

#include <stdio.h>

struct small {
    unsigned int a : 1;
    unsigned int b : 1;
    unsigned int c : 1;
};  // 总共 3 位 → sizeof = 4 (对齐到 unsigned int)

struct medium {
    unsigned int a : 16;
    unsigned int b : 16;
};  // 总共 32 位 → sizeof = 4 (刚好一个 unsigned int)

struct large {
    unsigned int a : 16;
    unsigned int b : 16;
    unsigned int c : 1;
};  // 总共 33 位 → sizeof = 8 (超出 32 位，需要两个 unsigned int)

int main(void)
{
    printf("sizeof(small)  = %zu\n", sizeof(struct small));   // 4
    printf("sizeof(medium) = %zu\n", sizeof(struct medium));  // 4
    printf("sizeof(large)  = %zu\n", sizeof(struct large));   // 8
    return 0;
}

5.3 位域与大端小端（回顾 Lesson 12）

位域的存储布局强烈依赖于字节序——同一段代码在大端和小端机器上的内存布局完全不同。这就是为什么 Linux 内核的 TCP 头定义需要同时处理两种字节序：

tcp_header_bitfield.c

// 来自 include/linux/tcp.h 的 TCP 协议头定义
struct tcphdr {
    __be16  source;      // 源端口 (大端)
    __be16  dest;        // 目的端口 (大端)
    __be32  seq;         // 序列号 (大端)
    __be32  ack_seq;     // 确认号 (大端)

#if defined(__LITTLE_ENDIAN_BITFIELD)
    // 小端机器：低地址存低位
    __u16   res1:4,      // 保留
            doff:4,      // 数据偏移
            fin:1,       // FIN 标志
            syn:1,       // SYN 标志
            rst:1,       // RST 标志
            psh:1,       // PSH 标志
            ack:1,       // ACK 标志
            urg:1,       // URG 标志
            ece:1,       // ECE 标志
            cwr:1;       // CWR 标志
#elif defined(__BIG_ENDIAN_BITFIELD)
    // 大端机器：低地址存高位（字段顺序反转！）
    __u16   doff:4,
            res1:4,
            cwr:1,
            ece:1,
            urg:1,
            ack:1,
            psh:1,
            rst:1,
            syn:1,
            fin:1;
#endif

    __be16  window;      // 窗口大小
    __sum16 check;       // 校验和
    __be16  urg_ptr;     // 紧急指针
};

IMPORTANT

位域的跨平台移植需要极其谨慎。回顾 Lesson 12 中学到的——小端机器上低字节在低地址，而大端机器上高字节在低地址。这导致位域内成员的排列顺序在两个平台上完全相反。如果你写的代码需要在不同平台上运行，要么避免使用位域，要么像 Linux 内核那样用条件编译分别处理。

5.4 位域 vs 位运算手动操作

对比维度	位域 bit-field	位运算手动操作
语法可读性	`flags.is_keyword = 1` 直观	`flags \|= 1 << 0` 需心算
跨平台一致性	依赖编译器和大端小端	完全由代码控制
空间效率	编译器自动紧凑排列	手动控制
适用场景	协议头、标志寄存器、码流	算法实现、跨平台代码
C 标准支持	实现定义行为较多	行为确定

建议：教学和跨平台代码中，优先使用位运算手动操作。位域在嵌入式开发、协议解析中有其便利性，但需了解其平台依赖性。

6. 位运算的优先级全解析

6.1 完整的优先级表

位运算在 C 语言运算符优先级中的位置（从高到低）：

优先级从高到低:

最高
  ()  []  ->  .                          (函数调用、下标、成员访问)
  !  ~  ++  --  +  -  *  &  (type)     (一元运算符，~ 在这里！)
  *  /  %                                (乘除取模)
  +  -                                   (加减)
  <<  >>                                 (移位)         ← 位运算从这里开始
  <  <=  >  >=                           (关系)
  ==  !=                                 (判等)
  &                                      (按位与)       ← 低于判等！
  ^                                      (按位异或)
  |                                      (按位或)
  &&                                     (逻辑与)
  ||                                     (逻辑或)
  ?:                                     (三元条件)
  =  +=  -=  <<=  &=  ...               (赋值)
最低

6.2 常见优先级错误

precedence_demo.c

#include <stdio.h>

int main(void)
{
    int a = 0x55;   // 0101 0101
    int mask = 0x0F;

    // 错误 1: & 优先级低于 ==
    if (a & mask == 0)
        printf("this is WRONG!\n");  // 等价于 a & (mask == 0)
    // mask == 0 → 0 (false)
    // a & 0 → 0
    // 条件总是为假！

    if ((a & mask) == 0)             // 正确：先做位与，再判等
        printf("low 4 bits are zero\n");

    // 错误 2: << 优先级低于 +
    int x = 1 << 2 + 1;              // 等价于 1 << (2+1) = 1 << 3 = 8
    printf("1 << 2 + 1 = %d (wrong!)\n", x);

    int y = (1 << 2) + 1;            // 正确: (1 << 2) + 1 = 4 + 1 = 5
    printf("(1 << 2) + 1 = %d (correct)\n", y);

    // 错误 3: & 优先级低于 !=
    int status = 0x4000;
    if (status & 0x4000 != 0)        // 等价于 status & (0x4000 != 0)
        printf("wrong logic!\n");

    if ((status & 0x4000) != 0)      // 正确
        printf("bit 14 is set\n");

    return 0;
}

CAUTION

铁律：任何时候把位运算和比较运算放在同一个表达式中，必须加括号。不要依赖优先级记忆——即使你记得住，读你代码的人也记不住。

7. 位运算的经典应用场景

7.1 用位运算实现 set_bit 和 get_bit

set_get_bit.c

#include <stdio.h>

// 将 num 的第 pos 位设置为 v (v 只能是 0 或 1)
int set_bit(int num, int pos, int v)
{
    if (v)
        return num | (1 << pos);      // 设置: 用 | 把第 pos 位置 1
    else
        return num & ~(1 << pos);     // 清除: 用 & ~ 把第 pos 位置 0
}

// 获取 num 的第 pos 位 (返回 0 或 1)
int get_bit(int num, int pos)
{
    return (num >> pos) & 1;          // 右移 pos 位，取最低位
}

int main(void)
{
    int a = 0x00;

    a = set_bit(a, 3, 1);   // 设置第 3 位 → 0x08 (0000 1000)
    printf("after set bit 3:  0x%02x\n", a);

    a = set_bit(a, 0, 1);   // 设置第 0 位 → 0x09 (0000 1001)
    printf("after set bit 0:  0x%02x\n", a);

    printf("bit 3 = %d\n", get_bit(a, 3));  // 1
    printf("bit 1 = %d\n", get_bit(a, 1));  // 0

    a = set_bit(a, 3, 0);   // 清除第 3 位 → 0x01
    printf("after clear bit 3: 0x%02x\n", a);

    return 0;
}

7.2 用异或实现字符大小写转换

case_toggle.c

#include <stdio.h>

int main(void)
{
    // ASCII 编码中，大写字母和小写字母只差第 5 位 (0x20)
    // 'A' = 0x41 = 0100 0001
    // 'a' = 0x61 = 0110 0001
    //               ↑ 只有第 5 位不同！

    // 方法 1: 异或翻转第 5 位
    char c1 = 'A';
    printf("%c ^ 0x20 = %c\n", c1, c1 ^ 0x20);  // A → a

    char c2 = 'z';
    printf("%c ^ 0x20 = %c\n", c2, c2 ^ 0x20);  // z → Z

    // 方法 2: 测试第 5 位后修改
    char c3 = 'H';
    if (c3 & 0x20)           // 第 5 位为 1 → 小写
        c3 &= ~0x20;         // 清除第 5 位 → 大写
    else                     // 第 5 位为 0 → 大写
        c3 |= 0x20;          // 设置第 5 位 → 小写
    printf("toggled: %c\n", c3);  // H → h

    // 演示：连续两次异或恢复原值
    char c4 = 'X';
    printf("%c → %c → %c\n", c4, c4 ^ 0x20, (c4 ^ 0x20) ^ 0x20);
    // X → x → X

    return 0;
}

ASCII 编码中，大写字母（0x41-0x5A）和小写字母（0x61-0x7A）的二进制表示只差一个位——第 5 位（从 0 开始计数，即 0x20）。因此翻转第 5 位就能实现大小写互转。

7.3 用位运算打印二进制

print_binary.c

#include <stdio.h>

// 打印一个无符号整数的二进制表示
void print_bin(unsigned int a)
{
    // 从最高位 (bit 31) 到最低位 (bit 0)
    for (int i = 31; i >= 0; i--)
    {
        printf("%d", (a >> i) & 1);

        // 每 4 位加一个空格，便于阅读
        if (i % 4 == 0 && i != 0)
            printf(" ");
    }
    printf("\n");
}

int main(void)
{
    unsigned int a = 31;  // 0x1F
    printf("a = %u\n", a);
    printf("binary: ");
    print_bin(a);
    // 输出: 0000 0000 0000 0000 0000 0000 0001 1111

    a = 0xDEADBEEF;
    printf("a = 0x%X\n", a);
    printf("binary: ");
    print_bin(a);
    // 输出: 1101 1110 1010 1101 1011 1110 1110 1111

    return 0;
}

类似地，八进制打印和十六进制打印只需要改变每次提取的位数和掩码：

print_oct_hex.c

#include <stdio.h>

// 打印八进制（每 3 位一组）
void print_oct(unsigned int a)
{
    // 32 位中，八进制需要 11 组 (3×11=33，最高位单独处理)
    int started = 0;
    for (int i = 30; i >= 0; i -= 3)
    {
        int digit = (a >> i) & 0x7;  // 提取 3 位
        if (digit != 0 || started || i == 0) {
            printf("%o", digit);     // 或用 %d 直接打印数字
            started = 1;
        }
        if (i > 0 && i % 6 == 0)
            printf(" ");
    }
    printf("\n");
}

// 打印十六进制（每 4 位一组）
void print_hex(unsigned int a)
{
    for (int i = 28; i >= 0; i -= 4)
    {
        printf("%X", (a >> i) & 0xF);
        if (i > 0 && i % 8 == 0)
            printf(" ");
    }
    printf("\n");
}

int main(void)
{
    unsigned int a = 31;  // 0x1F
    printf("a = %u\n", a);
    printf("oct:  "); print_oct(a);   // 0 0 0 ... 0 3 7
    printf("hex:  "); print_hex(a);   // 00 00 00 1F

    return 0;
}

7.4 用位运算实现无重复随机数生成

unique_random_bits.c

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

int main(void)
{
    srand(time(NULL));

    unsigned int used = 0;   // bit0-bit9 记录 0-9 哪些数字已生成
    int count = 0;

    while (count < 10)
    {
        int num = rand() % 10;           // 生成 0~9 的随机数

        if (!(used & (1 << num)))        // 第 num 位还是 0 → 未使用
        {
            used |= (1 << num);           // 标记第 num 位为 1
            printf("%d ", num);
            count++;
        }
        // 如果 num 已经生成过 → 跳过，重新生成
    }
    printf("\n");

    // 展示 used 的位图
    printf("used bitmap = 0x%03x\n", used);
    // 10 个 bit 全为 1 → 0x3FF

    return 0;
}

这里用一个整数的低 10 位作为"标记数组"——每位对应一个数字 0~9，生成过则置 1。这比用 int used[10] 数组更节省空间，也是位运算在算法中的经典应用。

参考解答

练习1: 逐位检测

solution_bit_by_bit.c

#include <stdio.h>

int count_bits(int num)
{
    int sum = 0;
    int i;

    for (i = 0; i < 32; i++)
        if (num & (1 << i))
            sum++;

    return sum;
}

int main(void)
{
    int num;
    scanf("%d", &num);
    printf("%d\n", count_bits(num));
    return 0;
}

也可以用 (num >> i) & 0x01 替代 num & (1 << i)——两种写法等价。前者把待检测位移到最低位，后者用移动的掩码去测试。循环上界写 32 或 sizeof(int) * 8 均可，前者直接但不够可移植，后者更具普适性。

练习2: n & (n-1) 清最低位

solution_n_and_nminus1.c

#include <stdio.h>

int count_bits(int num)
{
    int counter = 0;

    while (num != 0)
    {
        num &= (num - 1);    // 清除最右边的 1
        counter++;
    }

    return counter;
}

int main(void)
{
    int num;
    scanf("%d", &num);
    printf("%d\n", count_bits(num));
    return 0;
}

关键理解：n & (n-1) 利用二进制的借位减法特性，每次恰好清除最右边的 1。循环次数等于 1 的个数——对于 1024 (0x400)，只循环 1 次；对于 -1 (0xFFFFFFFF)，循环 32 次。

练习3: popcount 分治法

solution_popcount.c

#include <stdio.h>

#define M1  0x55555555
#define M2  0x33333333
#define M3  0x0F0F0F0F
#define M4  0x00FF00FF
#define M5  0x0000FFFF

int count_bits(int num)
{
    int sum = num;

    sum = (sum & M1) + ((sum >>  1) & M1);
    sum = (sum & M2) + ((sum >>  2) & M2);
    sum = (sum & M3) + ((sum >>  4) & M3);
    sum = (sum & M4) + ((sum >>  8) & M4);
    sum = (sum & M5) + ((sum >> 16) & M5);

    return sum;
}

int main(void)
{
    int num;
    scanf("%d", &num);
    printf("%d\n", count_bits(num));
    return 0;
}

5 层分治对应 5 个掩码——M1 到 M5 的二进制模式分别是 0101...、0011...、00001111...、0000000011111111...、0000...00001111...1111。每层把相邻两组合并，经过 5 层后 32 位的 1 的个数就被压缩到最低位。时间复杂度 O(1)，固定 10 条位运算指令。

对照检查：练习 1 中循环次数是 32（不是 31）？练习 2 中 while 条件是 num != 0？练习 3 中每层都正确使用了掩码 & Mk？popcount 的 5 层顺序不能调换——每层依赖于上一层将"小组合并"的结果。

课堂讨论

逐位检测算法和 n & (n-1) 算法各有什么优缺点？什么场景下应该用哪个？
n & (n-1) 为什么恰好清除最右边的 1 而不是最左边的 1？如果 n 是负数（补码表示），这个操作还能正常工作吗？
popcount 分治法中，为什么每层都需要 & Mk 掩码？如果去掉掩码会发生什么？
位域 bit-field 和普通结构体有什么本质区别？在什么场合下位域比手动位运算更好？
回顾 Lesson 04 中学到的奇偶判断——num & 1 和 num % 2 在判断奇偶时是否等价？对于负数呢？（提示：C99 规定 % 的结果符号与被除数相同）

讨论答案

Q1: 逐位检测 vs n&(n-1) 的取舍？

两种算法的核心差异在循环次数：

compare_two_methods.c

// 方法 1: 逐位检测 — 总是 32 次
int count_bits_v1(int n) {
    int c = 0;
    for (int i = 0; i < 32; i++)
        if (n & (1 << i)) c++;
    return c;
}

// 方法 2: n & (n-1) — 1 的个数次
int count_bits_v2(int n) {
    int c = 0;
    while (n) { n &= n - 1; c++; }
    return c;
}

方法 1 的优势：

循环次数固定，便于编译器优化（循环展开）
对初学者最直观——"检查每一位"的思维无需额外理解
可方便扩展到其他位操作（如统计 0 的个数、找最高位的 1）

方法 2 的优势：

循环次数 = 1 的个数，稀疏数据效率极高
代码更简洁——3 行核心逻辑
n & (n-1) 本身就是重要知识点，理解后可用于判断 2 的幂、子集枚举等场景

建议：教学中先学方法 1 建立位运算基础，再学方法 2 感受算法优化的巧妙。实际工程中两种都用——简单场景用方法 1（清晰），性能敏感场景用方法 2 或编译器内置 __builtin_popcount。

Q2: n&(n-1) 为什么清除最右边而非最左边？负数能正常工作吗？

为什么是最右边的 1：减法 n-1 从最低位开始借位。设 n 的最右边 1 在位置 k，则 n-1 把第 k 位变成 0、第 k 位右边所有 0 变成 1。n & (n-1) 保留第 k 位左边的所有位（n 和 n-1 相同），清除第 k 位及右边所有位——所以恰好清除最右边的 1。

n = 0b...1 0 0 0
n-1=0b...0 1 1 1    ← 借位：k 位变 0，右边全变 1
&  =0b...0 0 0 0    ← 第 k 位及右边全清零

负数能正常工作吗？ 完全可以！因为 n & (n-1) 是纯位运算，不依赖数值的正负。

negative_n_and_nminus1.c

#include <stdio.h>

int main(void)
{
    int n = -1;  // 补码: 0xFFFFFFFF (32 个 1)
    int c = 0;
    while (n) {
        n &= n - 1;
        c++;
    }
    printf("count of 1 in -1 = %d\n", c);  // 输出 32 ✓

    n = -8;  // 补码: 0xFFFFFFF8 (29 个 1)
    c = 0;
    while (n) {
        n &= n - 1;
        c++;
    }
    printf("count of 1 in -8 = %d\n", c);  // 输出 29 ✓

    return 0;
}

补码表示下 n & (n-1) 同样清除最右边二进制位的 1——它与符号无关。

Q3: popcount 每层为什么需要 & Mk？去掉会怎样？

掩码的作用：防止跨组数据泄漏。

why_mask_needed.c

#include <stdio.h>

int main(void)
{
    unsigned int x = 0xFFFFFFFF;

    // 正确：带掩码
    unsigned int good = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    printf("with mask:    0x%08x\n", good);
    // 每 2 位组: 01+01=10, 结果 0xAAAAAAAA (每 2 位都是 10 = 2)

    // 错误：不带掩码
    unsigned int bad = (x & 0x55555555) + (x >> 1);
    printf("without mask: 0x%08x\n", bad);
    // 0x55555555 + 0x7FFFFFFF = 0xD5555554 ← 完全错误！
    // 移位后相邻组的高位"污染"了当前组的计算结果

    return 0;
}

具体原因：x >> 1 后，每个 2 位组中不仅包含了原始该组的"高位移到低位"的数据，还包含了下一组低位溢出到当前组高位的数据。& 0x55555555 的作用就是屏蔽这些溢出位，保证每组独立计算。

第 5 层（M5 = 0x0000FFFF）的掩码在某些实现中可以省略，因为 32 位加法中高 16 位 + 低 16 位最多等于 32，不会溢出到第 17 位及以上。但保留掩码使代码模式统一。

Q4: 位域和普通结构体的本质区别？什么场合用位域更好？

本质区别：

bitfield_vs_struct.c

// 普通结构体：每个成员至少占 1 字节
struct normal {
    unsigned int a : 1;  // 还是占 4 字节！（unsigned int 对齐）
    unsigned int b : 1;
};
// 如果改成 unsigned char：
struct normal_char {
    unsigned char a : 1;
    unsigned char b : 1;
};  // sizeof = 1 (两个位域共用一个字节)

// 位域结构体：成员以位为单位紧凑排列
struct bitfield {
    unsigned char a : 1;  // 占 1 位
    unsigned char b : 1;  // 占 1 位
    unsigned char c : 1;  // 占 1 位
    unsigned char d : 5;  // 占 5 位
};  // sizeof = 1 (8 位刚好一个字节)

位域更适合的场景：

协议头解析：TCP/IP 头中很多字段只有几位（如 TCP flags 各占 1 位，data offset 占 4 位）
硬件寄存器映射：外设的状态寄存器中不同位代表不同含义
紧凑标志集合：大量布尔标志需要节省内存时
码流解析：视频/音频编码中位级别的数据解析

位运算更适合的场景：

跨平台代码：位域的内存布局依赖编译器和大端小端
算法实现：如 popcount、CRC、加密算法等需要精确控制位操作
教学和面试：理解位运算的底层原理

Q5: num & 1 和 num % 2 判断奇偶是否完全等价？

对于非负数：完全等价。num & 1 检查最低位是否为 1（偶数为 0，奇数为 1），num % 2 返回除以 2 的余数。

对于负数（回顾 Lesson 04）：C99 规定 % 的结果符号与被除数相同，因此：

mod_vs_bitwise.c

#include <stdio.h>

int main(void)
{
    // 正数：完全一致
    printf(" 7 & 1 = %d,  7 %% 2 = %d\n", 7 & 1, 7 % 2);    // 1, 1
    printf(" 8 & 1 = %d,  8 %% 2 = %d\n", 8 & 1, 8 % 2);    // 0, 0

    // 负数：结果可能不同！
    printf("-7 & 1 = %d, -7 %% 2 = %d\n", -7 & 1, -7 % 2);  // 1, -1
    printf("-8 & 1 = %d, -8 %% 2 = %d\n", -8 & 1, -8 % 2);  // 0,  0

    // 判断奇偶性时：
    // num & 1: 非零为奇 → -7 & 1 = 1 → 奇数 ✓
    // num % 2: 非零为奇 → -7 % 2 = -1 (非零) → 奇数 ✓
    // 判断逻辑上两者等价——关键是用 != 0 而非 == 1 来判断

    return 0;
}

结论：判断奇偶性时两者等价，但 num & 1 通常更快（位运算 vs 除法）。如果只需判断"是否为奇数"，用 num & 1；如果需要余数（包括符号信息），用 num % 2。

课后练习

实现 set_bit 和 get_bit 接口：编写 set_bit(int num, int pos, int v) 和 get_bit(int num, int pos) 函数，支持设置和读取任意位置的位。
知识点提示：set_bit 中 v 为 1 时用 | 置位，为 0 时用 & ~ 清除。get_bit 用 (num >> pos) & 1 提取。
用位运算实现字符大小写转换：编写程序，输入大写字母转为小写，输入小写字母转为大写。用两种方法实现——异或法和测试后修改法。
知识点提示：ASCII 编码中大写字母和小写字母只差第 5 位（0x20）。异或 0x20 翻转该位；也可以先测试 c & 0x20 再决定置位还是清除。
用位运算实现进制打印：编写 print_bin、print_oct、print_hex 三个函数，分别以二进制、八进制、十六进制格式打印一个无符号整型。
知识点提示：二进制每次提取 1 位（掩码 0x1），八进制每次提取 3 位（掩码 0x7），十六进制每次提取 4 位（掩码 0xF）。从高位向低位逐组提取并打印。
用位域实现无重复随机数：用位域（或位运算）实现随机生成无重复的 10 个数字（0-9），要求不允许使用数组。用一个整型数的 bit0-bit9 来记录已经产生的数字。
知识点提示：rand() 生成随机数，used & (1 << num) 检查是否已生成，used |= (1 << num) 标记已生成。回顾 srand(time(NULL)) 设置随机种子。
位运算实现加法：不用 + 运算符，仅用位运算实现两个整数的加法 int bit_add(int a, int b)。
知识点提示：异或 ^ 得到无进位和，与 & 再左移 << 1 得到进位。循环直到进位为 0：sum = a ^ b; carry = (a & b) << 1; a = sum; b = carry;。

练习1: set_bit 和 get_bit

ex1_set_get_bit.c

#include <stdio.h>

int set_bit(int num, int pos, int v)
{
    if (v)
        return num | (1 << pos);
    else
        return num & ~(1 << pos);
}

int get_bit(int num, int pos)
{
    return (num >> pos) & 1;
}

int main(void)
{
    int a = 0x00;

    a = set_bit(a, 5, 1);   // 设置第 5 位 → 0x20
    printf("set bit 5: 0x%02x\n", a);

    a = set_bit(a, 2, 1);   // 设置第 2 位 → 0x24
    printf("set bit 2: 0x%02x\n", a);

    printf("bit 5 = %d\n", get_bit(a, 5));  // 1
    printf("bit 1 = %d\n", get_bit(a, 1));  // 0

    a = set_bit(a, 5, 0);   // 清除第 5 位 → 0x04
    printf("clear bit 5: 0x%02x\n", a);

    return 0;
}

核心模式：num | (1 << pos) 置位，num & ~(1 << pos) 清除，(num >> pos) & 1 提取。这三个模式是嵌入式开发和硬件编程中最常用的位操作原语。

练习2: 字符大小写转换

ex2_case_toggle.c

#include <stdio.h>

int main(void)
{
    char c;

    printf("input a letter: ");
    scanf("%c", &c);

    // 方法 1: 异或翻转第 5 位
    printf("method 1 (xor): %c\n", c ^ 0x20);

    // 方法 2: 测试第 5 位后修改
    char result = c;
    if (result & 0x20)         // 第 5 位为 1 → 小写字母
        result &= ~0x20;       // 清除第 5 位 → 大写
    else                        // 第 5 位为 0 → 大写字母
        result |= 0x20;        // 设置第 5 位 → 小写
    printf("method 2 (test): %c\n", result);

    return 0;
}

关键知识：'A' = 0x41 (0100 0001)，'a' = 0x61 (0110 0001)。两者只差第 5 位（0x20）。异或 0x20 直接翻转该位，一行代码完成转换。注意这个方法只适用于字母——如果输入数字或符号，结果可能不是合法字符。

练习3: 进制打印

ex3_print_base.c

#include <stdio.h>

void print_bin(unsigned int a)
{
    for (int i = 31; i >= 0; i--)
    {
        printf("%d", (a >> i) & 1);
        if (i % 4 == 0 && i != 0)
            printf(" ");
    }
    printf("\n");
}

void print_oct(unsigned int a)
{
    // 32 位需要 11 组八进制数字 (3×11=33, 最高位单独处理)
    for (int i = 30; i >= 0; i -= 3)
    {
        printf("%o", (a >> i) & 0x7);
        if (i > 0 && i % 6 == 0)
            printf(" ");
    }
    printf("\n");
}

void print_hex(unsigned int a)
{
    for (int i = 28; i >= 0; i -= 4)
    {
        printf("%X", (a >> i) & 0xF);
        if (i > 0 && i % 8 == 0)
            printf(" ");
    }
    printf("\n");
}

int main(void)
{
    unsigned int a = 31;

    printf("a = %u\n", a);
    printf("bin: "); print_bin(a);
    // 0000 0000 0000 0000 0000 0000 0001 1111

    printf("oct: "); print_oct(a);
    // 0 0 0 0 0 0 0 0 0 3 7

    printf("hex: "); print_hex(a);
    // 00 00 00 1F

    return 0;
}

核心模式：右移 + 掩码提取 + 格式化打印。二进制每次右移 1 位用 & 1 提取，八进制每次右移 3 位用 & 0x7 提取，十六进制每次右移 4 位用 & 0xF 提取。

练习4: 无重复随机数

ex4_unique_random.c

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

int main(void)
{
    srand(time(NULL));

    unsigned int used = 0;
    int count = 0;

    printf("10 unique random numbers (0-9): ");
    while (count < 10)
    {
        int num = rand() % 10;

        if (!(used & (1 << num)))       // 第 num 位还未使用
        {
            used |= (1 << num);          // 标记为已使用
            printf("%d ", num);
            count++;
        }
    }
    printf("\n");

    printf("used bitmap = 0x%03X\n", used);  // 应为 0x3FF
    return 0;
}

用 unsigned int 的低 10 位（bit0-bit9）作为 10 个布尔标记——比 int used[10] 数组更紧凑。used & (1 << num) 检查第 num 位，used |= (1 << num) 置位。10 个数字全部生成后 used == 0x3FF (二进制 1111111111)。

练习5: 位运算实现加法

ex5_bit_add.c

#include <stdio.h>

int bit_add(int a, int b)
{
    while (b != 0)                 // 还有进位就继续
    {
        int carry = (a & b) << 1;  // 计算进位（两个位都为 1 时才产生进位）
        a = a ^ b;                 // 无进位和（异或：0+0=0, 0+1=1, 1+0=1, 1+1=0）
        b = carry;                 // 把进位作为下一轮的加数
    }
    return a;
}

int main(void)
{
    printf("15 + 27 = %d\n", bit_add(15, 27));     // 42
    printf("100 + 200 = %d\n", bit_add(100, 200)); // 300
    printf("-5 + 3 = %d\n", bit_add(-5, 3));       // -2
    return 0;
}

手动追踪 bit_add(5, 3)：

a=5(0101), b=3(0011):
  carry = (0101 & 0011) << 1 = 0001 << 1 = 0010
  a = 0101 ^ 0011 = 0110
  b = 0010

a=6(0110), b=2(0010):
  carry = (0110 & 0010) << 1 = 0010 << 1 = 0100
  a = 0110 ^ 0010 = 0100
  b = 0100

a=4(0100), b=4(0100):
  carry = (0100 & 0100) << 1 = 0100 << 1 = 1000
  a = 0100 ^ 0100 = 0000
  b = 1000

a=0(0000), b=8(1000):
  carry = (0000 & 1000) << 1 = 0000
  a = 0000 ^ 1000 = 1000 = 8
  b = 0 → 退出，返回 8 ✓

这是计算机底层加法器（全加器）的软件模拟——异或得到"半加和"，与+左移得到"进位"，反复迭代直到没有进位。

参考资料

Bit Twiddling Hacks (Sean Eron Anderson) — 位运算技巧大全，包含 popcount 分治法等多种高效实现
Hamming Weight (Wikipedia) — 汉明重量（popcount）的数学定义与多种算法对比
SWAR: SIMD Within A Register — 在一个寄存器内并行处理多个数据的技术思想
ISO C99 Standard, Section 6.7.2.1 — 结构体和位域的标准规范
TCP Header Format — TCP 协议头中位域的实际应用案例

"Premature optimization is the root of all evil." — Donald Ervin Knuth

Lesson 15: 统计二进制 1 的个数 ​CNB

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 位运算基础：C 语言的二进制操作 ​

1.1 六种位运算符一览 ​

1.2 常见位操作模式 ​

1.3 位运算优先级的致命陷阱 ​

2. 逐位检测算法：位运算的直观入门 ​

2.1 算法原理 ​

2.2 为什么循环 32 次？ ​

2.3 循环次数分析 ​

3. n & (n-1)：一个魔法般的位运算技巧 ​

3.1 算法原理 ​

3.2 为什么 n & (n-1) 恰好清除最右边的 1？ ​

3.3 不同输入的行为对比 ​

3.4 算法优势分析 ​

3.5 n & (n-1) 的其他妙用 ​

4. popcount 分治法：5 步完成 O(1) 统计 ​

4.1 从逐位求和到并行加法 ​

4.2 第 1 层：每 2 位一组 ​

4.3 完整 5 层分治 ​

4.4 完整追踪示例 ​

4.5 掩码的规律 ​

4.6 为什么需要 & 掩码？ ​

4.7 时间复杂度分析 ​

5. 位域 bit-field：以位为单位的数据结构 ​

5.1 位域的基本语法 ​

5.2 位域的内存布局 ​

5.3 位域与大端小端（回顾 Lesson 12） ​

5.4 位域 vs 位运算手动操作 ​

6. 位运算的优先级全解析 ​

6.1 完整的优先级表 ​

6.2 常见优先级错误 ​

7. 位运算的经典应用场景 ​

7.1 用位运算实现 set_bit 和 get_bit ​

7.2 用异或实现字符大小写转换 ​

7.3 用位运算打印二进制 ​

7.4 用位运算实现无重复随机数生成 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​