Java中获取long类型最低有效置位（LSB）索引的问题

问题描述 #

原代码用于获取int类型最低有效置位的索引，但处理long类型且最低有效置位为第64位（即值为0b1000000000000000000000000000000000000000000000000000000000000000L，也就是Long.MIN_VALUE）时，返回0而非预期的64。

原代码：

public class Test{
    public static void main(String[] args){
        long test = 0b1000000000000000000000000000000000000000000000000000000000000000L;
        
        //this should print "64"
        System.out.println(getLSBIndx(test));
    }
    public static int getLSBIndx(long n){
        if(n == 0) return -1;
        return (int)((Math.log10(n & -n)) / Math.log10(2)) ;
    }
}

问题根源 #

1. 负数参数导致NaN：当n为Long.MIN_VALUE时，n & -n的结果仍是Long.MIN_VALUE（补码特性：-Long.MIN_VALUE等于自身），而Math.log10不接受负数参数，返回NaN，强制转换为int后得到0。
2. 浮点数精度误差：即使是正数，大整数的对数计算可能因浮点数精度限制出现偏差，导致结果不准确。

最优解决方案 #

方案1：使用Java内置方法（推荐，Java 8+） #

利用Long.numberOfTrailingZeros方法，它直接返回long值中最低设置位后面的零的个数，最低有效置位的索引（从1开始计数）即为该值加1：

public class Test{
    public static void main(String[] args){
        long test = 0b1000000000000000000000000000000000000000000000000000000000000000L;
        
        // 输出64
        System.out.println(getLSBIndx(test));
    }
    public static int getLSBIndx(long n){
        if(n == 0) return -1;
        return Long.numberOfTrailingZeros(n) + 1;
    }
}

方案2：手动位运算实现（兼容低版本Java） #

通过位运算计算最低置位掩码的位数，避免浮点数问题：

public static int getLSBIndx(long n) {
    if (n == 0) return -1;
    long mask = n & -n;
    int count = 0;
    while (mask != 0) {
        mask >>>= 1;
        count++;
    }
    return count;
}

如果追求更高效率，可使用二分法减少循环次数：

public static int getLSBIndx(long n) {
    if (n == 0) return -1;
    long mask = n & -n;
    int pos = 0;
    if ((mask & 0xFFFFFFFF00000000L) != 0) { pos += 32; mask >>>= 32; }
    if ((mask & 0x00000000FFFF0000L) != 0) { pos += 16; mask >>>= 16; }
    if ((mask & 0x000000000000FF00L) != 0) { pos += 8; mask >>>= 8; }
    if ((mask & 0x00000000000000F0L) != 0) { pos += 4; mask >>>= 4; }
    if ((mask & 0x000000000000000CL) != 0) { pos += 2; mask >>>= 2; }
    if ((mask & 0x0000000000000002L) != 0) { pos += 1; }
    return pos + 1;
}

内容的提问来源于stack exchange，提问作者user2220139