妙用位运算：解构汉明距离至100%（提供分析与多解）

名称Doubletful的博客算法专栏签名路漫漫其修远兮吾将上下而求索文章目录前言一、二进制计算简介1.二进制操作符1.1.位操作符1.2.移位操作符2.进制转换二、题目解法一 操作符遍历统计解法二Brian Kernighan 算法遍历统计解法三掩码分治统计三、总结四、练习前言在数字世界的底层万物皆为二进制当我们比较两个整数时一个有趣的度量方式不是看它们数值差多少而是看它们在二进制形态下“长得有多不像”这种度量在信息论中被称为汉明距离。文章概述本文将使用 c 语言通解 LeetCode 题目461. 汉明距离。将提供三种逐步优化的解法使时间复杂度缩短至 O(1)。提供基础位运算简介以便初学者阅读可跳过。一、二进制计算简介1.二进制操作符1.1.位操作符按位与 按照对应的二进制位进行与运算同时为1才为1二进制例1100 0011 00001010 1000 1000。按位或 |按照对应的二进制位进行或运算同时为0才为0二进制例1100 | 0011 11111010 | 1000 1010。按位异或 ^按照对应的二进制位进行异或运算相同为0相异为1二进制例1100 ^ 0011 11111010 ^ 1000 0010。按位取反 ~按照对应的二进制位进行取反运算将0和1互换二进制例~1100 0011~1010 0101~1000 0111。1.2.移位操作符左移操作符 语法为被移动整数 移动位数规则是左边丢弃右边填充0。二进制例00011000 1 00110000。右移操作符 语法为被移动整数 移动位数规则分为两种情况逻辑右移和算术右移大部分编译器采用算术右移。逻辑右移左边填充0右边丢弃。算术右移左边用该值的符号位填充右边丢弃。二进制例00011000 1 00001100。注位操作符和移位操作符都只能对整数进行操作。2.进制转换⇒二进制转八进制从二进制的低位开始每3个二进制位转换为一个八进制位剩余直接转化。例二进制为 10111八进制为 27十进制为 23。⇒二进制转十六进制从二进制的低位开始每4个二进制位转换为一个十六进制位剩余直接转化。例二进制为 1010011十六进制为 53十进制为 83。接下来是正题部分二、题目先看题目我们被要求计算两个 32 位整数的汉明距离即 x 与 y 不同二进制位的个数。解法一 操作符遍历统计首先计算 x ^ y。异或运算的本质是“相同为0不同为1”因此新 x 的二进制表示中有多少个 1就代表原数有多少个不同的位。利用 操作符遍历 x 的每一位并使用 操作符判断 x 的每一位是否为 1 记录不同位的个数。解法二Brian Kernighan 算法遍历统计有一个极其巧妙的位运算性质n (n - 1) 的结果会将 n 的二进制中最右边的 1 变为 0图例如下设有一个二进制数为 10000当这个数减 1 时结果是 0111110000 01111 正好等于 0因为每次减 1 都会使二进制数上最右边的 1 退位使在该数位前的全 0 位变为全 1 位并将该数位变为 0 操作正好就将减 1 前的二进制数与减 1 后的二进制数有 1 的位全部对应有 0 的位抹除最右边的 1。解法三掩码分治统计这是本篇文章的重头戏也是计算机底层架构如 CPU 指令 POPCNT实现统计 1 个数的数学原理。它不再依赖循环而是通过二分法将位数累加。初看代码会非常奇怪这些十六进制数代表什么意思为什么 x 要 这些数后又将 x 右移并再次 它们为什么这样就能计算新 x 中为 1 的二进制位个数了——我们逐步拆解先看这些十六进制数代表什么一个十六进制位等于四个二进制位将这些十六进制数转换为二进制后0x55555555 0101 0101 0101 0101 0101 0101 0101 01010x33333333 0011 0011 0011 0011 0011 0011 0011 00110x0f0f0f0f 0000 1111 0000 1111 0000 1111 0000 11110x00ff00ff 0000 0000 1111 1111 0000 0000 1111 11110x0000ffff 0000 0000 0000 0000 1111 1111 1111 1111可以观察到有一定规律它们的二进制特征分别是0x55555555单个位交替用于隔离相邻的奇偶位0x33333333两位交替用于隔离相邻的 4 位中的低 2 位0x0F0F0F0F四位交替用于隔离相邻的 8 位中的低 4 位0x00FF00FF八位交替用于隔离相邻的 16 位中的低 8 位0x0000FFFF 十六位交替用于隔离高 16 位和低 16 位这些位中的 0 都用于隔离1 都用于保留计算0x55555555 的作用有些特殊它先以每 1 位统计 x 中 1 的个数并将个数存储进对应的两位中也就是先转换将代表 x 与 y 在哪一位不同的 1 转换为以每两位分隔的实际不同位的数量注意该意义转换目前只在每两位中生效。而除 0x55555555 以外的值都在做被分隔的实际不同位数量的合并操作最终合并为 32 位表示的实际不同位数量也就是正确的十进制表示。 运算、 运算与加法解读在理解了这些数字在代码中的作用后再看 x 分别直接进行 运算和 x 先右移再进行 运算就非常通俗易懂了如下所示❇️2 位一组将 x 分为每 2 位一组计算每组中 1 的个数。x 0x55555555 取出奇数位的 1右移后取出偶数位的 1二者相加结果以二进制形式保存在原来的 2 位空间中。❇️4 位一组将上一步的结果每 4 位一组计算每组中 1 的个数。x 0x33333333 先取出前两位的个数右移后再取出后两位的个数最后相加结果以二进制形式保存在原来的 4 位空间中。……………………❇️归并到 32 位最终得到整个 32 位整数中 1 的总数。三、总结通过这道经典的汉明距离题目我们清晰地看到了算法演进的三个层次解法核心思想优点缺点解法一逐位右移检查直观易懂符合第一反应固定循环 32 次存在冗余操作解法二清除最低位的 1循环次数仅与 1 的个数有关实战效率高依然依赖循环无法利用现代 CPU 并行特性解法三二进制并行加法树状归并无分支、无循环性能极致体现了位运算的数学之美可读性较差需要深刻理解二进制分治原理四、练习推荐手动在LeetCode网站上实现三种解法461. 汉明距离 链接link.⚛️EL PSY CONGROO十分感谢你的阅读本期不确定是否应该添加掩码分治统计执行图例