最低位 1 的位置

题目描述

给定一个整数 n，请输出它的二进制表示中 最低位的 1 出现在第几位（从 0 开始计数）。

• 例如：
  • n = 12 (1100) → 最低位的 1 在第 2 位；
  • n = 18 (10010) → 最低位的 1 在第 1 位；
  • n = 20 (10100) → 最低位的 1 在第 2 位。

输入格式

输入一个整数 n。

输出格式

输出一个整数，表示最低位的 1 在第几位。

数据范围

• 1 ≤ n ≤ 10^9 （保证 n > 0，所以一定至少有一个 1）

输入输出样例

输入 1

12

输出 1

2

输入 2

18

输出 2

1

思路提示

• 方法 1：逐位判断
  • 从低位到高位逐一检查 (n >> i) & 1 是否为 1；
  • 第一次发现 1 的位置就是答案。
• 方法 2：位运算技巧
  • n & -n 可以快速得到最低位的 1 所在的值（是 $2^k$）；
  • 再用 __builtin_ctz(n)（count trailing zeros，gcc/clang 提供）可以直接得到位置。