java Long.highestOneBit lowestOneBit位运算

这两个方法是 java.lang.Long 类提供的静态工具方法，用于位运算操作，返回 long 值中最高或最低设置位（即值为 1 的位）对应的 2 的幂。

方法签名

// 返回最高位的 1 所对应的值（即最左边的 1）
public static long highestOneBit(long i)

// 返回最低位的 1 所对应的值（即最右边的 1）
public static long lowestOneBit(long i)

• 参数：i - 要操作的 long 值
• 返回值：一个 long 值，表示最高/最低位 1 的位置对应的 2 的幂
• 异常：无（包括 0 和负数都有定义行为）

功能说明

💡 关键理解：

• 返回的是数值，不是位置索引。
• 例如：12 的二进制是 1100，最高位 1 在第 3 位（从 0 开始），对应值 8（即 2^3），最低位 1 在第 2 位，对应值 4（即 2^2）。

示例代码

1. 基本使用

long value = 12; // 二进制: 1100

System.out.println(Long.toBinaryString(value));     // 1100
System.out.println(Long.highestOneBit(value));      // 8  (1000)
System.out.println(Long.lowestOneBit(value));       // 4  (0100)

long value2 = 17; // 二进制: 10001
System.out.println(Long.highestOneBit(value2));     // 16 (10000)
System.out.println(Long.lowestOneBit(value2));      // 1  (00001)

2. 特殊值处理

// 零值
System.out.println(Long.highestOneBit(0));   // 0
System.out.println(Long.lowestOneBit(0));    // 0

// 1
System.out.println(Long.highestOneBit(1));   // 1
System.out.println(Long.lowestOneBit(1));    // 1

// 2 的幂（如 8 = 1000）
System.out.println(Long.highestOneBit(8));   // 8
System.out.println(Long.lowestOneBit(8));    // 8

3. 负数处理（补码）

// 负数使用补码表示，所有位都参与计算
long negative = -8;
// -8 的补码（简化）: ...1111111111111000 (64 位)
System.out.println(Long.toBinaryString(negative).substring(58)); 
// 输出最后几位: 1000 （实际前面全是 1）

System.out.println(Long.highestOneBit(negative)); // -9223372036854775808
// 即 0x8000000000000000，表示符号位（第 63 位）

System.out.println(Long.lowestOneBit(negative));  // 8
// 最低位的 1 是第 3 位，对应 2^3 = 8

使用技巧

✅ 技巧1：判断是否为 2 的幂

public static boolean isPowerOfTwo(long x) {
    return x > 0 && Long.highestOneBit(x) == x;
    // 或更高效：x > 0 && (x & (x - 1)) == 0;
}

✅ 技巧2：获取数字的“尺度”（Scale）

// 获取一个数在二进制下的“位长度”（近似 log2）
int bitLength = 63 - Long.numberOfLeadingZeros(value);
// 或等价于：
long highest = Long.highestOneBit(value);
int log2 = Long.numberOfTrailingZeros(highest); // 因为 highest 是 2^n

✅ 技巧3：清除最低位的 1（常见位运算技巧）

// 清除最低位的 1：x & (x - 1)
long x = 12; // 1100
long cleared = x & (x - 1); // 1100 & 1011 = 1000 = 8

✅ 技巧4：遍历所有为 1 的位

long value = 12; // 1100
while (value != 0) {
    long lowest = Long.lowestOneBit(value);
    System.out.println("Found bit: " + lowest); // 输出 4, 然后 8
    value -= lowest; // 或 value &= value - 1;
}

常见错误

❌ 错误1：混淆“位置”与“值”

// 错误理解
// Long.highestOneBit(12) 返回的是 8（值），不是 3（位置）

// 正确获取位置：
int pos = 63 - Long.numberOfLeadingZeros(12); // 3

❌ 错误2：认为负数没有最高位

// 错误：以为负数的 highestOneBit 是 0
// 实际：负数的最高位是符号位（第 63 位），返回的是 Long.MIN_VALUE
System.out.println(Long.highestOneBit(-1)); // -9223372036854775808

❌ 错误3：对 0 的行为误解

// 正确：0 的最高/最低位都是 0
System.out.println(Long.highestOneBit(0)); // 0
System.out.println(Long.lowestOneBit(0));  // 0

注意事项

1. 返回值是数值：不是索引，而是 2^n 的形式。
2. 负数处理：基于补码，highestOneBit 对负数总是返回 Long.MIN_VALUE（即 -2^63）。
3. 零值：输入 0 时，两个方法都返回 0。
4. 性能优秀：JVM 内部使用高效位运算实现（如 BSR/BSF 指令）。
5. 线程安全：静态方法，无状态，线程安全。

最佳实践与性能优化

🔧 性能建议

• 这两个方法性能极高，通常被 JVM 内联为单条 CPU 指令。
• 在算法中常用于位掩码生成、树结构索引计算（如 Fenwick Tree）、哈希表扩容等。

底层原理简析

• highestOneBit(i) 实现类似：

  i = i | (i >>> 1);
  i = i | (i >>> 2);
  i = i | (i >>> 4);
  i = i | (i >>> 8);
  i = i | (i >>> 16);
  i = i | (i >>> 32);
  return i - (i >>> 1);
  

  （实际 JVM 使用 numberOfLeadingZeros 更高效）

• lowestOneBit(i) 等价于：i & (-i)（经典位运算技巧）

总结

💡 一句话掌握：
Long.highestOneBit(x) 找最左的 1，Long.lowestOneBit(x) 找最右的 1，
返回的是对应的 2 的幂值，不是位置，
是位运算中的高效工具方法，常用于算法优化。