当前位置: 首页 > article >正文

算法基础 -- Brian Kernighan 算法初识

Brian Kernighan 算法:利用 x & (x - 1) 逐步清除最低位的 1

1. 算法原理
  • x & (x - 1) 这个操作的作用是每次清除 x 的最低位的 1
  • 由于 二进制的减法 会影响最低的 1,我们可以利用这一特性不断去除 1,直到 x 变为 0,从而统计 1 的个数
2. x & (x - 1) 操作的数学推导

对于任意正整数 x,可以用二进制表示:
x = ... 1000 ... 000 x = \text{...} 1000\text{...}000 x=...1000...000
(假设 x 的最低位的 1 出现在某个位置)

x - 1 计算时,二进制的减法规则会导致:

  • 最低位的 1 变为 0
  • 它右边的所有 0 变为 1(因为 -1 相当于借位操作)。

举例:

x     =  101000    // 40
x - 1 =  100111    // 39
x & (x - 1) = 100000  // 结果 32,最低的 1 被清除

可以看到:

  • x - 1x 最低的 1 变成 0,并把右侧所有 0 变成 1
  • x & (x - 1) 就只保留了 x 中比最低 1 更高的位,消除了最低位 1

一般性证明:
x 的二进制最低 1 位于 k 位置(从右向左,从 0 开始编号),则:

  • x = ...1000...000(最低位 1k 处)
  • x - 1 = ...0111...111k 位置变成 0,右侧全变 1

执行 x & (x - 1)
x & ( x − 1 ) = ( . . . 1000...000 ) & ( . . . 0111...111 ) = ( . . . 0000...000 ) x \& (x - 1) = (...1000...000) \& (...0111...111) = (...0000...000) x&(x1)=(...1000...000)&(...0111...111)=(...0000...000)
可见,最低的 1 被消除。


3. 代码实现
#include <stdio.h>

int count_bits(uint32_t x) {
    int count = 0;
    while (x) {
        x &= (x - 1);  // 每次清除最低位的1
        count++;
    }
    return count;
}

int main() {
    uint32_t x = 0b10110101101100011011000101101010; // 示例数据
    printf("Number of 1s: %d\n", count_bits(x));
    return 0;
}
4. 代码解析
  1. 初始化 count = 0,用于存储 1 的个数。
  2. 循环执行 x &= (x - 1)
    • 每次清除 x 的最低位 1
    • count++ 统计已经清除的 1 的数量。
  3. 循环终止条件是 x == 0,即 x 所有 1 都被清除。

5. 运行示例

假设 x = 0b10110101101100011011000101101010(等于 3073836458),二进制如下:

10110101101100011011000101101010

逐步消除最低位的 1

10110101101100011011000101101010  // x
10110101101100011011000101101001  // x - 1
--------------------------------
10110101101100011011000101101000  // x & (x - 1)

10110101101100011011000101101000
10110101101100011011000101100111
--------------------------------
10110101101100011011000101100000

10110101101100011011000101100000
10110101101100011011000101011111
--------------------------------
10110101101100011011000101000000

...

不断重复,直到 x = 0

最终 循环运行 19,输出:

Number of 1s: 19

6. 时间复杂度分析

假设 x 的位数是 n(32 位),设 x 里有 k1,则:

  • 每次操作都减少一个 1,因此总共执行 k 次操作。
  • 最坏情况下 O(n)x 的 32 位全是 1,如 0xFFFFFFFF)。
  • 最好情况下 O(1)x = 0b10000000000000000000000000000000,只执行一次)。
  • 均摊复杂度 O(1),因为实际数据往往 1 的个数远少于 32

相比逐位检查

  • 逐位检查的复杂度始终是 O(n),即最多执行 32 次
  • x & (x - 1) 只执行 O(k)k 通常远小于 n,因此速度更快。

7. 适用场景
方案复杂度适用情况
逐位检查x >> 1O(n)适用于所有情况,但效率较低
Brian KernighanO(k)适用于 1 数量较少的情况
POPCNT 指令O(1)最优解,适用于现代 CPU
查表法O(1)适用于大批量数据

结论

  • 单个整数计算x & (x - 1) 是 CPU 无特殊指令时的最优选择
  • 处理大量整数__builtin_popcount(x) 或查表法更快

8. 拓展:其他 x & (x - 1) 的应用
  1. 判断 x 是否是 2 的幂x 只有一个 1
int is_power_of_2(uint32_t x) {
    return x && !(x & (x - 1));
}

示例

8 (0b1000)  -> x & (x - 1) = 0
10 (0b1010) -> x & (x - 1) = 8 (!= 0)
  1. 计算 x 的最低位 1 的位置
int lowest_bit_position(uint32_t x) {
    return x & -x;
}

示例

x = 40 (0b101000)  -> x & -x = 8 (0b1000)

9. 结论
  • x & (x - 1) 是一个强大的二进制操作,可以用来快速统计 1 的个数,适用于 CPU 没有 POPCNT 指令的情况。
  • 时间复杂度 O(k),其中 k1 的个数,比逐位检查更快。
  • 还能用于判断 x 是否是 2 的幂、提取最低位的 1 等多种用途。

http://www.kler.cn/a/586339.html

相关文章:

  • 基础知识《HTTP字段与状态码详细说明》
  • 【基于 SSE 协议与 EventSource 实现 AI 对话的流式交互】
  • Stable Diffusion API /sdapi/v1/txt2img的完整参数列表及其说明
  • leetcode hot 100(三)
  • python全栈-MySQL知识
  • MySQL:MySQL库和表的基本操作
  • SpringBoot实现一个Redis限流注解
  • Springboot项目修改端口
  • 深入理解Spring Boot:快速构建现代化的Java应用
  • 【调研】模型输出内容的json形式content怎样处理可以转换为json?
  • kafka生成者发送消息失败报错:RecordTooLargeException
  • MCU的工作原理:嵌入式系统的控制核心
  • Elasticsearch:语义文本 - 更简单、更好、更精炼、更强大 8.18
  • Hot100算法刷题:双指针
  • c# 利用mv-cs200-10gc工业相机,识别液注的高度
  • ubuntu-学习笔记-nextjs部署相关
  • QT:文件读取
  • Webpack优化前端性能
  • SQL--算术运算符
  • MATLAB风光柴储微网粒子群算法