lowbit函数

C++中lowbit函数的实现方式详解

lowbit函数的核心思想是利用位运算快速找到一个数二进制表示中最低位的1所对应的值。下面我将详细解释几种常见的实现方式，并通过具体例子说明其工作原理。

1. 使用x & -x实现（最常用）

cpp

复制

下载

int lowbit(int x) {return x & -x;
}

原理说明：

• -x在计算机中是以补码表示的，等于~x + 1（取反加一）

• 这个操作会把x的最低位的1保留下来，而其他位都取反

• 再与原数x做与运算，就只保留了最低位的1

示例分析：
以x=6为例（二进制0110）：

1. x = 6 = 0110

2. -x = ~x + 1 = 1001 + 1 = 1010

3. x & -x = 0110 & 1010 = 0010 = 2

2. 使用x & (x ^ (x - 1))实现

cpp

复制

下载

int lowbit(int x) {return x & (x ^ (x - 1));
}

原理说明：

• x - 1会把最低位的1变成0，后面的0都变成1

• x ^ (x - 1)会产生一个从最低位1开始往右全是1的数

• 再与x做与运算就得到最低位的1

示例分析：
以x=12为例（二进制1100）：

1. x = 12 = 1100

2. x - 1 = 11 = 1011

3. x ^ (x - 1) = 1100 ^ 1011 = 0111

4. x & (x ^ (x - 1)) = 1100 & 0111 = 0100 = 4

3. 使用x - (x & (x - 1))实现

cpp

复制

下载

int lowbit(int x) {return x - (x & (x - 1));
}

原理说明：

• x & (x - 1)会消去x的最低位的1

• 用x减去这个结果就得到了被消去的那个1对应的值

示例分析：
以x=10为例（二进制1010）：

1. x = 10 = 1010

2. x - 1 = 9 = 1001

3. x & (x - 1) = 1010 & 1001 = 1000

4. x - (x & (x - 1)) = 1010 - 1000 = 0010 = 2

性能比较

1. x & -x是最简洁高效的方式，只需要两次操作（取负和与运算）

2. 其他方法需要3-4次操作，效率稍低

3. 现代编译器通常会对这些操作进行优化

实际应用示例

cpp

复制

下载

#include <iostream>
#include <bitset>void printLowbit(int x) {int lb = x & -x;std::cout << "lowbit(" << x << " = 0b" << std::bitset<8>(x) << ") = " << lb << " = 0b" << std::bitset<8>(lb) << std::endl;
}int main() {printLowbit(6);    // 6 = 0b00000110 → 2 = 0b00000010printLowbit(12);   // 12 = 0b00001100 → 4 = 0b00000100printLowbit(7);    // 7 = 0b00000111 → 1 = 0b00000001printLowbit(16);   // 16 = 0b00010000 → 16 = 0b00010000return 0;
}

输出结果：

text

复制

下载

lowbit(6 = 0b00000110) = 2 = 0b00000010
lowbit(12 = 0b00001100) = 4 = 0b00000100
lowbit(7 = 0b00000111) = 1 = 0b00000001
lowbit(16 = 0b00010000) = 16 = 0b00010000

在实际编程中，x & -x是最推荐使用的实现方式，因为它简洁高效且易于理解。

关于lowbit函数的系统自带情况

lowbit函数不是C++标准库或系统自带的函数，它是算法竞赛和位操作编程中常用的一个自定义工具函数。

常见实现位置

由于lowbit不是标准函数，它通常出现在以下地方：

1. 算法竞赛代码模板中：

   • 经常出现在树状数组(BIT/Fenwick Tree)的实现中

   • 或者位运算相关的算法模板中

2. 自定义头文件/工具库中：

   • 一些程序员会把它放在自己的工具头文件中，如bit_utils.h

3. 在线判题系统的预定义代码中：

   • 某些OJ平台可能在预包含代码中提供

类似功能的系统函数

虽然标准库没有直接的lowbit函数，但有一些相关功能：

1. <bit>头文件(C++20引入)：

   cpp

   复制

   下载

   #include <bit>
   int lsb = std::countr_zero(x);  // 返回最低位1的位置(从0开始)
   int lowbit = 1 << lsb;          // 等价于lowbit

2. GCC内置函数：

   cpp

   复制

   下载

   int lsb = __builtin_ffs(x) - 1;  // 返回最低位1的位置(从1开始)
   int lowbit = 1 << lsb;

推荐实践

如果你需要频繁使用lowbit函数，建议：

1. 在自己的工具头文件中定义：

   cpp

   复制

   下载

   // bit_utils.h
   #pragma onceinline int lowbit(int x) {return x & -x;
   }

2. 或者在需要使用的地方直接定义：

   cpp

   复制

   下载

   auto lowbit = [](int x) { return x & -x; };

3. 如果是C++20环境，可以使用标准库方式：

   cpp

   复制

   下载

   #include <bit>auto lowbit = [](auto x) { return x == 0 ? 0 : 1 << std::countr_zero(x); 
   };

记住，lowbit是一个编程实践中广泛使用的惯用法，而不是标准库的一部分，所以使用时需要自己实现或从可靠的代码库中引入。