https://ryanuo.cc/assets/bitwise-ByEVH2tT.js

1import{u as e,_ as i}from"./WrapPost.vue_vue_type_script_setup_true_lang-GcuoGZDg.js";import{c as d,o as r,w as p,a as s,b as l}from"./app-C9Wey_4Y.js";const B={__name:"bitwise",setup(h){const t={title:"位运算全解析：基础技巧、经典例题与嵌入式实战",date:"2024-07-18 08:55",cate:"笔记",description:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。",image:"https://ryanuo.cc/og/og-ryanuo.cc-posts-bitwise.png",meta:[{property:"og:title",content:"位运算全解析：基础技巧、经典例题与嵌入式实战"},{name:"twitter:title",content:"位运算全解析：基础技巧、经典例题与嵌入式实战"},{name:"description",content:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。"},{property:"og:description",content:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。"},{name:"twitter:description",content:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。"},{property:"og:image",content:"https://ryanuo.cc/og/og-ryanuo.cc-posts-bitwise.png"},{name:"twitter:image",content:"https://ryanuo.cc/og/og-ryanuo.cc-posts-bitwise.png"},{name:"twitter:card",content:"summary_large_image"}]};return e({title:"位运算全解析：基础技巧、经典例题与嵌入式实战",meta:[{property:"og:title",content:"位运算全解析：基础技巧、经典例题与嵌入式实战"},{name:"twitter:title",content:"位运算全解析：基础技巧、经典例题与嵌入式实战"},{name:"description",content:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。"},{property:"og:description",content:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。"},{name:"twitter:description",content:"六种位运算符、常用技巧速查（lowbit、位掩码、异或性质），配大量 LeetCode 经典例题的 C 语言实现，以及寄存器读改写、字节序转换等嵌入式实战场景。"},{property:"og:image",content:"https://ryanuo.cc/og/og-ryanuo.cc-posts-bitwise.png"},{name:"twitter:image",content:"https://ryanuo.cc/og/og-ryanuo.cc-posts-bitwise.png"},{name:"twitter:card",content:"summary_large_image"}]}),(k,a)=>{const n=i;return r(),d(n,{frontmatter:t},{default:p(()=>a[0]||(a[0]=[s("div",{class:"prose m-auto slide-enter-content"},[s("div",{class:"table-of-contents"},[s("div",{class:"table-of-contents-anchor"},[s("div",{class:"i-ri-menu-2-fill"})]),s("ul",null,[s("li",null,[s("a",{href:"#位运算基础"},"位运算基础"),s("ul",null,[s("li",null,[s("a",{href:"#一、六种运算符"},"一、六种运算符")]),s("li",null,[s("a",{href:"#二、异或的性质（重点）"},"二、异或的性质（重点）")]),s("li",null,[s("a",{href:"#三、避坑指南（c-语言）"},"三、避坑指南（C 语言）")])])]),s("li",null,[s("a",{href:"#常用技巧速查"},"常用技巧速查"),s("ul",null,[s("li",null,[s("a",{href:"#一、单-bit-操作（嵌入式基本功）"},"一、单 bit 操作（嵌入式基本功）")]),s("li",null,[s("a",{href:"#二、算术类"},"二、算术类")]),s("li",null,[s("a",{href:"#三、lowbit-与-2-的幂"},"三、lowbit 与 2 的幂")]),s("li",null,[s("a",{href:"#四、异或类"},"四、异或类")]),s("li",null,[s("a",{href:"#五、向上取整到-2-的幂"},"五、向上取整到 2 的幂")])])]),s("li",null,[s("a",{href:"#经典例题"},"经典例题"),s("ul",null,[s("li",null,[s("a",{href:"#一、统计二进制中-1-的个数（lc191）"},"一、统计二进制中 1 的个数（LC191）")]),s("li",null,[s("a",{href:"#二、比特位计数（lc338）"},"二、比特位计数（LC338）")]),s("li",null,[s("a",{href:"#三、只

1出现一次的数字（lc136）"},"三、只出现一次的数字（LC136）")]),s("li",null,[s("a",{href:"#四、只出现一次的数字-iii（lc260）"},"四、只出现一次的数字 III（LC260）")]),s("li",null,[s("a",{href:"#五、只出现一次的数字-ii（lc137）"},"五、只出现一次的数字 II（LC137）")]),s("li",null,[s("a",{href:"#六、丢失的数字（lc268）"},"六、丢失的数字（LC268）")]),s("li",null,[s("a",{href:"#七、颠倒二进制位（lc190）"},"七、颠倒二进制位（LC190）")]),s("li",null,[s("a",{href:"#八、2-的幂-4-的幂（lc231-lc342）"},"八、2 的幂 / 4 的幂（LC231 / LC342）")]),s("li",null,[s("a",{href:"#九、汉明距离（lc461）"},"九、汉明距离（LC461）")]),s("li",null,[s("a",{href:"#十、不用加号做加法（lc371）"},"十、不用加号做加法（LC371）")]),s("li",null,[s("a",{href:"#十一、数字范围按位与（lc201）"},"十一、数字范围按位与（LC201）")]),s("li",null,[s("a",{href:"#十二、格雷编码（lc89）"},"十二、格雷编码（LC89）")]),s("li",null,[s("a",{href:"#十三、最大单词长度乘积（lc318）"},"十三、最大单词长度乘积（LC318）")]),s("li",null,[s("a",{href:"#十四、判定字符是否全都不同（面试题-01-01）"},"十四、判定字符是否全都不同（面试题 01.01）")]),s("li",null,[s("a",{href:"#十五、位掩码枚举子集（lc78）"},"十五、位掩码枚举子集（LC78）")])])]),s("li",null,[s("a",{href:"#嵌入式实战"},"嵌入式实战"),s("ul",null,[s("li",null,[s("a",{href:"#一、寄存器读-改-写"},"一、寄存器读-改-写")]),s("li",null,[s("a",{href:"#二、大小端判断与字节序转换"},"二、大小端判断与字节序转换")]),s("li",null,[s("a",{href:"#三、用位图（bitmap）省内存"},"三、用位图（bitmap）省内存")])])]),s("li",null,[s("a",{href:"#速查小结"},"速查小结")])])]),s("h2",{id:"位运算基础",tabindex:"-1"},[l("位运算基础 "),s("a",{class:"header-anchor",href:"#位运算基础","aria-hidden":"true"},"#")]),s("h3",{id:"一、六种运算符",tabindex:"-1"},[l("一、六种运算符 "),s("a",{class:"header-anchor",href:"#一、六种运算符","aria-hidden":"true"},"#")]),s("table",null,[s("thead",null,[s("tr",null,[s("th",null,"运算符"),s("th",null,"名称"),s("th",null,"规则"),s("th",null,"示例（8 位）")])]),s("tbody",null,[s("tr",null,[s("td",null,[s("code",null,"&")]),s("td",null,"按位与"),s("td",null,"两位都为 1 才为 1"),s("td",null,[s("code",null,"0b1100 & 0b1010 = 0b1000")])]),s("tr",null,[s("td",null,[s("code",null,"|")]),s("td",null,"按位或"),s("td",null,"有一位为 1 即为 1"),s("td",null,[s("code",null,"0b1100 | 0b1010 = 0b1110")])]),s("tr",null,[s("td",null,[s("code",null,"^")]),s("td",null,"按位异或"),s("td",null,"两位不同为 1"),s("td",null,[s("code",null,"0b1100 ^ 0b1010 = 0b0110")])]),s("tr",null,[s("td",null,[s("code",null,"~")]),s("td",null,"按位取反"),s("td",null,"0 变 1，1 变 0"),s("td",null,[s("code",null,"~0b0000_1111 = 0b1111_0000")])]),s("tr",null,[s("td",null,[s("code",null,"<<")]),s("td",null,"左移"),s("td",null,"低位补 0"),s("td",null,[s("code",null,"0b0011 << 2 = 0b1100")])]),s("tr",null,[s("td",null,[s("code",null,">>")]),s("td",null,"右移"),s("td",null,"无符号补 0；有符号通常补符号位"),s("td",null,[s("code",null,"0b1100 >> 2 = 0b0011")])])])]),s("p",null,"三个核心运算的记忆口诀："),s("ul",null,[s("li",null,[s("code",null,"&"),l("："),s("strong",null,"清零、取位、判断"),l("（和掩码与，保留想要的位）")]),s("li",null,[s("code",null,"|"),l("："),s("strong",null,"置位"),l("（和掩码或，强制某些位为 1）")]),s("li",null,[s("code",null,"^"),l("："),s("strong",null,"翻转、去重、无进位加法")])]),s("h3",{id:"二、异或的性质（重点）",tabindex:"-1"},[l("二、异或的性质（重点） "),s("a",{class:"header-anchor",href:"#二、异或的性质（重点）","aria-hidden":"true"},"#")]),s("p",null,"异或是位运算题的核心，四条性质务必烂熟："),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-text"},[s("span",{class:"line"},[s("span",null,"x ^ 0 = x          （零元）")]),l(`
2`),s("span",{class:"line"},[s("span",null,"x ^ x = 0          （自反）")]),l(`
3`),s("span",{class:"line"},[s("span",null,"x ^ y = y ^ x      （交换律）")]),l(`
4`),s("span",{class:"line"},[s("span",null,"(x ^ y) ^ z = x ^ (y ^ z)   （结合律）")])])]),s("p",null,[l("推论："),s("strong",null,"一堆数异或到一起，出现偶数次的数全部抵消"),l("。这是「只出现一次的数字」系列题的根基。")]),s("h3",{id:"三、避坑指南（c-语言）",tabindex:"-1"},[l("三、避坑指南（C 语言） "),s("a",{class:"header-anchor",href:"#三、避坑指南（c-语言）","aria-hidden":"true"},"#")]),s("p",null,"写 C 的人必须知道的几个坑："),s("ol",null,[s("li",null,[s("strong",null,"优先级"),l("："),s("code",null,"&"),l("、"),s("code",null,"|"),l("、"),s("code",null,"^"),l(" 的优先级"),s("strong",null,"低于"),l(),s("code",null,"=="),l("、"),s("code",null,"!="),l("。"),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," =="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}}

4,"     // 错！等价于 x & (1 == 0)，恒为 0")]),l(`
5`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," =="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 对，判断偶数")])])])]),s("li",null,[s("strong",null,"移位量越界是 UB"),l("：移位位数 ≥ 类型位宽（如 "),s("code",null,"x << 32"),l("，x 为 32 位）是未定义行为。")]),s("li",null,[s("strong",null,[s("code",null,"1 << 31"),l(" 是 UB")]),l("：有符号 "),s("code",null,"int"),l(" 左移溢出未定义，操作最高位请用 "),s("code",null,"1u << 31"),l("。")]),s("li",null,[s("strong",null,"负数右移是实现定义"),l("：多数平台是算术右移（补符号位），但可移植代码不要依赖；需要逻辑右移时先转 "),s("code",null,"unsigned"),l("。 "),s("ul",null,[s("li",null,[l("对于无符号，右移一位等于 "),s("code",null,"x >> 1"),l(" 除以2（向下取整）。")])])]),s("li",null,[s("strong",null,"负数按补码参与位运算"),l("："),s("code",null,"-1"),l(" 的二进制是全 1（"),s("code",null,"0xFFFFFFFF"),l("），"),s("code",null,"~0 == -1"),l("。")]),s("li",null,[s("strong",null,"整数提升"),l("："),s("code",null,"uint8_t"),l(" 参与运算会先提升为 "),s("code",null,"int"),l("，"),s("code",null,"~"),l(" 一个 "),s("code",null,"uint8_t"),l(" 再比较时经常出意外，必要时强转回去。")])]),s("h2",{id:"常用技巧速查",tabindex:"-1"},[l("常用技巧速查 "),s("a",{class:"header-anchor",href:"#常用技巧速查","aria-hidden":"true"},"#")]),s("p",null,"以下技巧建议全部记住，面试和嵌入式开发使用频率极高。"),s("h3",{id:"一、单-bit-操作（嵌入式基本功）",tabindex:"-1"},[l("一、单 bit 操作（嵌入式基本功） "),s("a",{class:"header-anchor",href:"#一、单-bit-操作（嵌入式基本功）","aria-hidden":"true"},"#")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"  ("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"        // 置位：第 n 位置 1")]),l(`
6`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&="),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ~"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"        // 清位：第 n 位清 0")]),l(`
7`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"  ("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"        // 翻转第 n 位")]),l(`
8`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"          // 取第 n 位的值")])])]),s("h3",{id:"二、算术类",tabindex:"-1"},[l("二、算术类 "),s("a",{class:"header-anchor",href:"#二、算术类","aria-hidden":"true"},"#")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                   // 判断奇偶：1 奇 0 偶（比 x % 2 对负数更省心）")]),l(`
9`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," k"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                  // x * 2^k")]),l(`
10`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," k"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                  // x / 2^k（非负数）")]),l(`
11`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," k"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," -"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"     // x % 2^k（非负数），如 x & 15 即 x % 16")]),l(`
12`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 7"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ~"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"7"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"           // 向上对齐到 8 的倍数（内存对齐常用）")]),l(`
13`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"a "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," +"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"a "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"  // 平均值，不会像 (a+b)/2 那样溢出")])])]),s("h3",{id:"三、lowbit-与-2-的幂",tabindex:"-1"},[l("三、lowbit 与 2 的幂 "),s("a",{class:"header-anchor",href:"#三、lowbit-与-2-的幂","aria-hidden":"true"},"#")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                // lowbit：取出最低位的 1（树状数组核心）")]),l(`
14`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"             // 清除最低位的 1（Brian Kernighan）")]),l(`
15`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," =="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 判断是否为 2 的幂")])])]),s("p",null,[l("理解方式："),s("code",null,"x - 1"),l(" 会把最低位的 1 变 0、其后的 0 全变 1，因此 "),s("code",null,"x & (x-1)"),l(" 恰好抹掉最低位的 1；"),s("code",null,"-x"),l(" 是补码（"),s("code",null,"~x + 1"),l("），除最低位 1 及其后的 0 外全部取反，因此 "),s("code",null,"x & -x"),l(" 只剩最低位的 1。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-text"},[s("span",{class:"line"},[s("span",null,"x     = 0110 1000")]),l(`
16`),s("span",{class:"line"},[s("span",null,"x - 1 = 0110 0111")]),l(`
17`),s("span",{class:"line"},[s("span",null,"x&(x-1)=0110 0000   （抹掉最低位 1）")]),l(`
18`),s("span",{class:"line"},[s("span",null,"-x    = 1001 1000")]),l(`
19`),s("span",{class:"line"},[s("span",null,"x&(-x)= 0000 1000   （只留最低位 1）")])])]),s("h3",{id:"四、异或类",tabindex:"-1"},[l("四、异或类 "),s("a",{class:"header-anchor",href:"#四、异或类","aria-hidden":"true"},"#")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"a "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," a"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," a "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 交换两数（注意：a、b 是同一变量时会清零，实战别炫技）")]),l(`
20`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," y"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"               // 判断两数是否异号（无溢出风险）")]),l(`
21`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"c "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 32"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}}

21,"                    // 字母大小写互转（'A'^32='a'，'a'^32='A'）")])])]),s("h3",{id:"五、向上取整到-2-的幂",tabindex:"-1"},[l("五、向上取整到 2 的幂 "),s("a",{class:"header-anchor",href:"#五、向上取整到-2-的幂","aria-hidden":"true"},"#")]),s("p",null,"哈希表扩容、环形缓冲区容量常用："),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," next_pow2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," v"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
22`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
23`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    v"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"--"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
24`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
25`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
26`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 4"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
27`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 8"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
28`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 16"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
29`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," v "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // next_pow2(17) = 32, next_pow2(32) = 32")]),l(`
30`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("原理："),s("code",null,"v--"),l(" 后不断「或自身右移」，把最高位 1 以下全部刷成 1，最后 +1 进位。")]),s("h2",{id:"经典例题",tabindex:"-1"},[l("经典例题 "),s("a",{class:"header-anchor",href:"#经典例题","aria-hidden":"true"},"#")]),s("p",null,"以下题目按套路分组，全部给出 C 实现。每题先一句话点破思路。"),s("h3",{id:"一、统计二进制中-1-的个数（lc191）",tabindex:"-1"},[l("一、统计二进制中 1 的个数（LC191） "),s("a",{class:"header-anchor",href:"#一、统计二进制中-1-的个数（lc191）","aria-hidden":"true"},"#")]),s("p",null,[s("strong",null,[l("思路："),s("code",null,"x & (x-1)"),l(" 每次抹掉一个 1，有几个 1 循环几次。")])]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," hammingWeight"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
31`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
32`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," cnt "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
33`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    while"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
34`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 抹掉最低位的 1")]),l(`
35`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        cnt"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
36`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
37`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," cnt"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
38`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("进阶：无循环的 "),s("strong",null,"SWAR popcount"),l("（并行分治，先 2 位一组求和，再 4 位、8 位……）：")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," popcount"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," x"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
39`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
40`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    x "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"55555555"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                  // 每 2 位内统计")]),l(`
41`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    x "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"33333333"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," +"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"33333333"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 每 4 位内统计")]),l(`
42`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    x "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 4"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"0F0F0F0F"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                  // 每 8 位内统计")]),l(`
43`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"*"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"01010101"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 24"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"                    // 四个字节求和")]),l(`
44`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("实战直接用编译器内建 "),s("code",null,"__builtin_popcount(x)"),l("（GCC/Clang），会编译成硬件 "),s("code",null,"popcnt"),l(" 指令。")]),s("h3",{id:"二、比特位计数（lc338）",tabindex:"-1"},[l("二、比特位计数（LC338） "),s("a",{class:"header-anchor",href:"#二、比特位计数（lc338）","aria-hidden":"true"},"#")]),s("p",null,[l("求 0…n 每个数的二进制 1 的个数。"),s("strong",null,[l("思路：DP，"),s("code",null,"i"),l(" 的 1 个数 = "),s("code",null,"i>>1"),l(" 的 1 个数 + 最低位。")])]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"countBits"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"returnSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
45`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
46`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"dp "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," malloc"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"(("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," sizeof"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));")]),l(`
47`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"    dp"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`

48`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
49`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"        dp"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ="),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," dp"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," +"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
50`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"        // 等价写法：dp[i] = dp[i & (i - 1)] + 1;")]),l(`
51`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"returnSize "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
52`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," dp"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
53`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("h3",{id:"三、只出现一次的数字（lc136）",tabindex:"-1"},[l("三、只出现一次的数字（LC136） "),s("a",{class:"header-anchor",href:"#三、只出现一次的数字（lc136）","aria-hidden":"true"},"#")]),s("p",null,[l("其余数都出现两次。"),s("strong",null,"思路：全员异或，成对的抵消，剩下的就是答案。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," singleNumber"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
54`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
55`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
56`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
57`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        ans "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];")]),l(`
58`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
59`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("h3",{id:"四、只出现一次的数字-iii（lc260）",tabindex:"-1"},[l("四、只出现一次的数字 III（LC260） "),s("a",{class:"header-anchor",href:"#四、只出现一次的数字-iii（lc260）","aria-hidden":"true"},"#")]),s("p",null,[s("strong",null,"两个"),l("数出现一次，其余出现两次。"),s("strong",null,[l("思路：全员异或得 "),s("code",null,"x^y"),l("，取其 lowbit 把数组分成两组，组内各自异或。")])]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"singleNumber"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"returnSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
60`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
61`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    unsigned"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," xorall "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
62`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
63`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        xorall "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"unsigned"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];")]),l(`
64`),s("span",{class:"line"}),l(`
65`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    unsigned"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," lsb "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," xorall "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"~"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"xorall "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // lowbit；用 unsigned 规避 INT_MIN 取负的 UB")]),l(`
66`),s("span",{class:"line"}),l(`
67`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," calloc"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," sizeof"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));")]),l(`
68`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
69`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"unsigned"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," lsb"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
70`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"            ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ^="),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 该位为 1 的一组")]),l(`
71`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        else")]),l(`
72`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"            ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ^="),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // 该位为 0 的一组")]),l(`
73`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
74`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"returnSize "),s("spa

74n",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
75`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
76`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("关键："),s("code",null,"x^y != 0"),l("，它的任意一个为 1 的位都能把 x、y 分开，而成对的数必然进同一组。")]),s("h3",{id:"五、只出现一次的数字-ii（lc137）",tabindex:"-1"},[l("五、只出现一次的数字 II（LC137） "),s("a",{class:"header-anchor",href:"#五、只出现一次的数字-ii（lc137）","aria-hidden":"true"},"#")]),s("p",null,[l("其余数出现"),s("strong",null,"三次"),l("。"),s("strong",null,"思路：逐位统计 1 的个数，对 3 取模，余数就是答案在该位的值。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," singleNumber"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
77`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
78`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    unsigned"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
79`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 32"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
80`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"        int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," sum "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
81`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
82`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"            sum "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ((("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"unsigned"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"])"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
83`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"sum "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"%"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 3"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
84`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"            ans "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
85`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
86`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
87`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,"该解法可推广到「其余数出现 k 次」：对 k 取模即可。"),s("h3",{id:"六、丢失的数字（lc268）",tabindex:"-1"},[l("六、丢失的数字（LC268） "),s("a",{class:"header-anchor",href:"#六、丢失的数字（lc268）","aria-hidden":"true"},"#")]),s("p",null,[l("0…n 中缺一个。"),s("strong",null,"思路：把下标和数值全部异或，成对抵消，剩下缺的那个。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," missingNumber"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
88`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
89`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"              // 先补上下标 n")]),l(`
90`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," numsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
91`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        ans "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];")]),l(`
92`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
93`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("h3",{id:"七、颠倒二进制位（lc190）",tabindex:"-1"},[l("七、颠倒二进制位（LC190） "),s("a",{class:"header-anchor",href:"#七、颠倒二进制位（lc190）","aria-hidden":"true"},"#")]),s("p",null,[s("strong",null,"思路：分治蝶式交换——先交换高低 16 位，再 8 位、4 位、2 位、1 位。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," reverseBits"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
94`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
95`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    n "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 16"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 16"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
96`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    n "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"FF00FF00"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 8"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"00FF00FF"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 8"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
97`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    n "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"F0F0F0F0"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 4"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"

97--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"0F0F0F0F"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 4"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
98`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    n "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"CCCCCCCC"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"33333333"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 2"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
99`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"    n "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"AAAAAAAA"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"55555555"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
100`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
101`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,"嵌入式里做 CRC 反射（reflect）就是这套操作。"),s("h3",{id:"八、2-的幂-4-的幂（lc231-lc342）",tabindex:"-1"},[l("八、2 的幂 / 4 的幂（LC231 / LC342） "),s("a",{class:"header-anchor",href:"#八、2-的幂-4-的幂（lc231-lc342）","aria-hidden":"true"},"#")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"bool"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," isPowerOfTwo"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
102`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
103`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," =="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
104`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")]),l(`
105`),s("span",{class:"line"}),l(`
106`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"bool"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," isPowerOfFour"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
107`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
108`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"    // 先是 2 的幂，且唯一的 1 落在偶数位（bit 0/2/4...）")]),l(`
109`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," =="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &&"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"55555555"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," !="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
110`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("h3",{id:"九、汉明距离（lc461）",tabindex:"-1"},[l("九、汉明距离（LC461） "),s("a",{class:"header-anchor",href:"#九、汉明距离（lc461）","aria-hidden":"true"},"#")]),s("p",null,[l("两数二进制中不同位的个数。"),s("strong",null,"思路：异或后数 1。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," hammingDistance"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," x"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," y"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
111`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
112`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," __builtin_popcount"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," y"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
113`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("h3",{id:"十、不用加号做加法（lc371）",tabindex:"-1"},[l("十、不用加号做加法（LC371） "),s("a",{class:"header-anchor",href:"#十、不用加号做加法（lc371）","aria-hidden":"true"},"#")]),s("p",null,[s("strong",null,[l("思路："),s("code",null,"a ^ b"),l(" 是无进位和，"),s("code",null,"(a & b) << 1"),l(" 是进位，循环到进位为 0。")])]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}

113," getSum"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," a"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
114`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
115`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    while"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"b "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"!="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
116`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"        unsigned"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," carry "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"unsigned"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"a "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"   // unsigned 规避左移溢出 UB")]),l(`
117`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        a "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," a "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," b"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
118`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        b "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"carry"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
119`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
120`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," a"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
121`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,"这就是硬件加法器（半加器/全加器）的软件写法。"),s("h3",{id:"十一、数字范围按位与（lc201）",tabindex:"-1"},[l("十一、数字范围按位与（LC201） "),s("a",{class:"header-anchor",href:"#十一、数字范围按位与（lc201）","aria-hidden":"true"},"#")]),s("p",null,[l("求 [left, right] 区间所有数的 AND。"),s("strong",null,"思路：结果是 left 和 right 的公共二进制前缀，后面全为 0。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," rangeBitwiseAnd"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," left"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," right"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
122`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
123`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," shift "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
124`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    while"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"left "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," right"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}}

124,"   // 不断抹低位，直到剩公共前缀")]),l(`
125`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        left "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
126`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        right "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
127`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        shift"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
128`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
129`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," left "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," shift"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
130`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,"理解：只要区间长度跨过某位的进位，该位必然出现过 0，AND 后即为 0。"),s("h3",{id:"十二、格雷编码（lc89）",tabindex:"-1"},[l("十二、格雷编码（LC89） "),s("a",{class:"header-anchor",href:"#十二、格雷编码（lc89）","aria-hidden":"true"},"#")]),s("p",null,[l("相邻数只差一位的编码序列。"),s("strong",null,[l("结论：第 i 个格雷码 = "),s("code",null,"i ^ (i >> 1)"),l("。")])]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"grayCode"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"returnSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
131`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
132`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," size "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
133`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," malloc"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"size "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"*"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," sizeof"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));")]),l(`
134`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," size"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
135`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"        ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"^"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
136`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"returnSize "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," size"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
137`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
138`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,"格雷码在旋转编码器、异步 FIFO 跨时钟域中广泛使用——一次只变一位，杜绝采样毛刺。"),s("h3",{id:"十三、最大单词长度乘积（lc318）",tabindex:"-1"},[l("十三、最大单词长度乘积（LC318） "),s("a",{class:"header-anchor",href:"#十三、最大单词长度乘积（lc318）","aria-hidden":"true"},"#")]),s("p",null,[l("求两个不含公共字母的单词的最大长度积。"),s("strong",null,[l("思路：每个单词压成 26 位掩码，"),s("code",null,"mask[i] & mask[j] == 0"),l(" 即无公共字母。")])]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," maxProduct"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"char"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," **"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"words"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," wordsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
139`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
140`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"mask "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," calloc"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"wordsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," sizeof"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));")]),l(`
141`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"len  "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," calloc"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"wordsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," sizeof"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));")]),l(`
142`),s("span",{class:"line"}),l(`
143`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," wordsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
144`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"char"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"p "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," words"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"p"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," p"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
145`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"            mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"*"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"p "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}}," '"),s("span",{style:{"--s-dark":"#C98A7D","--s-light":"#B56959"}},"a"),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}},"'"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
146`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"        len"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," strlen"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"words"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]);")]),l(`
147`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
148`),s("span",{class:"line"}),l(`
149`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
150`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," wordsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
151`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{sty

151le:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," j "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"+"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," j "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," wordsSize"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," j"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
152`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"            if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"j"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"])"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," =="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &&"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," len"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," len"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"j"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
153`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"                ans "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," len"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," len"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"j"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];")]),l(`
154`),s("span",{class:"line"}),l(`
155`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"    free"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
156`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"    free"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"len"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
157`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," ans"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
158`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("「集合压缩成整数、集合运算变位运算」是状态压缩类题（旅行商、状压 DP）的通用套路：交集 "),s("code",null,"&"),l("、并集 "),s("code",null,"|"),l("、差集 "),s("code",null,"a & ~b"),l("、含于 "),s("code",null,"(a & b) == a"),l("。")]),s("h3",{id:"十四、判定字符是否全都不同（面试题-01-01）",tabindex:"-1"},[l("十四、判定字符是否全都不同（面试题 01.01） "),s("a",{class:"header-anchor",href:"#十四、判定字符是否全都不同（面试题-01-01）","aria-hidden":"true"},"#")]),s("p",null,[l("字符串仅小写字母，不用额外数据结构。"),s("strong",null,"思路：26 位掩码当 bool 数组。")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"bool"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," isUnique"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"char"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"astr"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
159`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
160`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," mask "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
161`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"char"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"p "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," astr"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"p"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," p"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
162`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"        int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"*"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"p "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}}," '"),s("span",{style:{"--s-dark":"#C98A7D","--s-light":"#B56959"}},"a"),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}},"'"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
163`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"mask "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
164`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"            return"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}}," false"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
165`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"        mask "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"|="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," bit"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
166`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
167`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}}," true"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
168`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("h3",{id:"十五、位掩码枚举子集（lc78）",tabindex:"-1"},[l("十五、位掩码枚举子集（LC78） "),s("a",{class:"header-anchor",href:"#十五、位掩码枚举子集（lc78）","aria-hidden":"true"},"#")]),s("p",null,"n 个元素的所有子集 = 0 … 2^n - 1 的所有二进制数，第 i 位为 1 表示选第 i 个元素。"),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"void"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," enumerate(int *nums, int n)")]),l(`
169`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
170`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," s "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," s "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," s"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"        // 每个 s 是一个子集")]),l(`
171`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"        for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 0"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"<"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"++"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
172`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"            if"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"s "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
173`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"                printf"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}},'"'),s("span",{style:{"--s-dark":"#C99076","--s-light":"#A65E2B"}},"%d"),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}},' "'),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," nums"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"i"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]);"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"          // 第 i 个元素被选中")]),l(`
174`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"        }")]),l(`
175`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"        printf"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}},'"'),s("span",{style:{"--s-dark":"#C99076","--s-light":"#A65E2B"}},"\\n"),s("span",{style:{"--s-dark":"#C98A7D77","--s-light":"#B5695977"}},'"'),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
176`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    }")]),l(`
177`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("进阶："),s("strong",null,"枚举某个掩码 mask 的全部子集"),l("（状压 DP 高频套路），复杂度 O(3^n)：")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"for"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," sub "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," mask"),s("span",{style:{"--s-dark":"#666666","--s-light

177":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," sub"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," sub "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"sub "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"-"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {")]),l(`
178`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"    // 处理非空子集 sub")]),l(`
179`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")]),l(`
180`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"// 需要空集则循环后单独处理一次 0")])])]),s("p",null,[l("原理："),s("code",null,"sub - 1"),l(" 会产生低位借位，再 "),s("code",null,"& mask"),l(" 把借出的位限制回 mask 内，恰好按降序遍历所有子集。")]),s("h2",{id:"嵌入式实战",tabindex:"-1"},[l("嵌入式实战 "),s("a",{class:"header-anchor",href:"#嵌入式实战","aria-hidden":"true"},"#")]),s("h3",{id:"一、寄存器读-改-写",tabindex:"-1"},[l("一、寄存器读-改-写 "),s("a",{class:"header-anchor",href:"#一、寄存器读-改-写","aria-hidden":"true"},"#")]),s("p",null,[l("操作外设寄存器的标准姿势——"),s("strong",null,"永远不要直接赋值整个寄存器，先读出、改目标位、再写回"),l("：")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"#"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"define"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"               ("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))")]),l(`
181`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"#"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"define"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," SET_BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"      (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"  BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))")]),l(`
182`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"#"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"define"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," CLEAR_BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &="),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ~"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))")]),l(`
183`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"#"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"define"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," TOGGLE_BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"   (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ^="),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"  BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))")]),l(`
184`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"#"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"define"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," READ_BIT"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"     ((("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"n"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
185`),s("span",{class:"line"}),l(`
186`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"/* 多位字段：先清掩码区域，再或上新值 */")]),l(`
187`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"#"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"define"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," MODIFY_FIELD"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," shift"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," val"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#C99076","--s-light":"#A65E2B"}}," \\")]),l(`
188`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"    (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"reg"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ~"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ((("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"val"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"shift"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"mask"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")))")]),l(`
189`),s("span",{class:"line"}),l(`
190`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"/* 例：设置波特率分频字段 [7:4] 为 0x5 */")]),l(`
191`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"MODIFY_FIELD"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"UART"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"->"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"CR"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"F0"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 4"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},","),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"5"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")])])]),s("p",null,[l("注意：寄存器变量必须声明为 "),s("code",null,"volatile"),l("，读-改-写非原子，中断和主循环同改一个寄存器时需要关中断或用硬件提供的原子置位/清位寄存器（如 STM32 的 BSRR）。")]),s("h3",{id:"二、大小端判断与字节序转换",tabindex:"-1"},[l("二、大小端判断与字节序转换 "),s("a",{class:"header-anchor",href:"#二、大小端判断与字节序转换","aria-hidden":"true"},"#")]),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," is_little_endian"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"void"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")")]),l(`
192`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
193`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"    uint16_t"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}}," x "),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";")]),l(`
194`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint8_t"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," *"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"=="),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}}

194,"   // 低地址存的是低字节 → 小端")]),l(`
195`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")]),l(`
196`),s("span",{class:"line"}),l(`
197`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," bswap32"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint32_t"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," x"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#758575DD","--s-light":"#A0ADA0"}},"      // 网络字节序（大端）互转")]),l(`
198`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"{")]),l(`
199`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}},"    return"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"FF000000"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 24"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |")]),l(`
200`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"           (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"00FF0000"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"  8"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |")]),l(`
201`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"           (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"0000FF00"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"  8"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |")]),l(`
202`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"           (("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"x "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," 0x"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"000000FF"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 24"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},");")]),l(`
203`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"}")])])]),s("p",null,[l("实战优先用 "),s("code",null,"htonl/ntohl"),l(" 或 GCC 的 "),s("code",null,"__builtin_bswap32"),l("，会编译成单条 "),s("code",null,"bswap"),l("/"),s("code",null,"rev"),l(" 指令。")]),s("h3",{id:"三、用位图

203（bitmap）省内存",tabindex:"-1"},[l("三、用位图（bitmap）省内存 "),s("a",{class:"header-anchor",href:"#三、用位图（bitmap）省内存","aria-hidden":"true"},"#")]),s("p",null,"1 个字节当 8 个布尔用，管理 1024 个资源只需 128 字节："),s("pre",{class:"shiki shiki-themes vitesse-dark vitesse-light",style:{"--s-dark":"#dbd7caee","--s-light":"#393a34","--s-dark-bg":"#121212","--s-light-bg":"#ffffff"},tabindex:"0"},[s("code",{class:"language-c"},[s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"uint8_t"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," bitmap"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"128"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"];")]),l(`
204`),s("span",{class:"line"}),l(`
205`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"static"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," inline"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," void"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," bm_set"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," id"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"   {"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," bitmap"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"id "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 3"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," |="),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"  ("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"id "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 7"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," }")]),l(`
206`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"static"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," inline"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," void"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}}," bm_clear"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," id"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," {"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," bitmap"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"id "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 3"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &="),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," ~"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}},"1"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"u"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," <<"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"id "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 7"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"));"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," }")]),l(`
207`),s("span",{class:"line"},[s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"static"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," inline"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," int"),s("span",{style:{"--s-dark":"#80A665","--s-light":"#59873A"}},"  bm_test"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"("),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"int"),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}}," id"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},")"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"  {"),s("span",{style:{"--s-dark":"#4D9375","--s-light":"#1E754F"}}," return"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#BD976A","--s-light":"#B07D48"}},"bitmap"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"["),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"id "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},">>"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 3"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"]"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," >>"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," ("),s("span",{style:{"--s-dark":"#DBD7CAEE","--s-light":"#393A34"}},"id "),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}},"&"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 7"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},"))"),s("span",{style:{"--s-dark":"#CB7676","--s-light":"#AB5959"}}," &"),s("span",{style:{"--s-dark":"#4C9A91","--s-light":"#2F798A"}}," 1"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}},";"),s("span",{style:{"--s-dark":"#666666","--s-light":"#999999"}}," }")])])]),s("p",null,[s("code",null,"id >> 3"),l(" 即 "),s("code",null,"id / 8"),l("，"),s("code",null,"id & 7"),l(" 即 "),s("code",null,"id % 8"),l("——除法取模全部退化成位运算。内核里的 fd 表、内存页分配器都是这个玩法。")]),s("h2",{id:"速查小结",tabindex:"-1"},[l("速查小结 "),s("a",{class:"header-anchor",href:"#速查小结","aria-hidden":"true"},"#")]),s("table",null,[s("thead",null,[s("tr",null,[s("th",null,"需求"),s("th",null,"写法")])]),s("tbody",null,[s("tr",null,[s("td",null,"判断奇偶"),s("td",null,[s("code",null,"x & 1")])]),s("tr",null,[s("td",null,"乘/除 2^k"),s("td",null,[s("code",null,"x << k"),l(" / "),s("code",null,"x >>

207 k")])]),s("tr",null,[s("td",null,"模 2^k"),s("td",null,[s("code",null,"x & ((1u << k) - 1)")])]),s("tr",null,[s("td",null,"置位 / 清位 / 翻转 / 取位"),s("td",null,[s("code",null,"x |= 1u<<n"),l(" / "),s("code",null,"x &= ~(1u<<n)"),l(" / "),s("code",null,"x ^= 1u<<n"),l(" / "),s("code",null,"(x>>n) & 1")])]),s("tr",null,[s("td",null,"取最低位 1（lowbit）"),s("td",null,[s("code",null,"x & -x")])]),s("tr",null,[s("td",null,"抹掉最低位 1"),s("td",null,[s("code",null,"x & (x - 1)")])]),s("tr",null,[s("td",null,"判断 2 的幂"),s("td",null,[s("code",null,"x > 0 && (x & (x-1)) == 0")])]),s("tr",null,[s("td",null,"判断异号"),s("td",null,[s("code",null,"(x ^ y) < 0")])]),s("tr",null,[s("td",null,"大小写互转"),s("td",null,[s("code",null,"c ^ 32")])]),s("tr",null,[s("td",null,"防溢出平均值"),s("td",null,[s("code",null,"(a & b) + ((a ^ b) >> 1)")])]),s("tr",null,[s("td",null,"无进位加法"),s("td",null,[s("code",null,"a ^ b"),l("，进位 "),s("code",null,"(a & b) << 1")])]),s("tr",null,[s("td",null,"集合交 / 并 / 差 / 包含"),s("td",null,[s("code",null,"a & b"),l(" / "),s("code",null,"a | b"),l(" / "),s("code",null,"a & ~b"),l(" / "),s("code",null,"(a & b) == a")])]),s("tr",null,[s("td",null,"枚举 mask 的子集"),s("td",null,[s("code",null,"sub = (sub - 1) & mask")])]),s("tr",null,[s("td",null,"第 i 个格雷码"),s("td",null,[s("code",null,"i ^ (i >> 1)")])])])]),s("p",null,[l("一句话总结：位运算的核心套路就三条——"),s("strong",null,[l("掩码（& 取、| 置、^ 翻）、lowbit 家族（"),s("code",null,"x&-x"),l("、"),s("code",null,"x&(x-1)"),l("）、异或抵消")]),l("，配合「整数当集合用」的状态压缩思想，能覆盖绝大多数题目和底层开发场景。")])],-1)])),_:1,__:[0]})}}};export{B as default};