java - 检查最小-最大堆 java 的奇偶级别

Question

这是我编写的一个方法，用于确定数组的给定索引是否表示堆的最大级别或最小级别，其中最小级别具有偶数深度(包括 0)，最大级别具有奇数深度。它工作得很好，但它的运行时间是(我认为)O(log N)。有没有更有效的方法来做到这一点，例如具有恒定运行时间的简单数学计算？请注意，此方法假设数据从数组的索引 1 开始，而不是从索引 0 开始。

    private boolean isMaxLevel(int i)
    {
    int border = 1;
    int prev = 1;
    int count = 1;
    boolean isMax = false;
    // alternates boolean between true and false as each level is checked.
    while (true)
        {
        if (i >= prev && i <= border)
            return isMax;
        isMax = !isMax;
        prev = border + 1;
        count *= 2;
        border += count;
    }
}

Answer 1

我不清楚您的要求是什么，但这可能对您有帮助。

public static void main(String... args) {
    for (int i = 1; i <= 256; i *= 2) {
        System.out.println((i - 1) + ": " + isOddHighestBit(i - 1));
        System.out.println(i + ": " + isOddHighestBit(i));
    }
}

public static boolean isOddHighestBit(int i) {
    return (Double.doubleToRawLongBits(i) >> 52) % 2 == 0;
}

打印

0: true
1: false
1: false
2: true
3: true
4: false
7: false
8: true
15: true
16: false
31: false
32: true
63: true
64: false
127: false
128: true
255: true
256: false