gpt4 book ai didi

java - 在 Java 中查找最左/最右未设置位的索引的最有效方法是什么?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:03:50 26 4
gpt4 key购买 nike

假设我们有 int x = 371,即二进制格式 101110011。我想找到最左边未设置位的索引(在本例中为 7)和最右边未设置位的索引(在本例中为 2)。最有效的方法是什么?

这是我所拥有的:

public class BitOperatons {

public static int setBit(int x, int i) {
int y = x | (1 << i);
return y;
}

public static boolean isBitSet(int x, int i) {
int y = setBit(0, i);
return y == (x & y);
}

public static int findLeftMostSetBit(int x) {
for (int i = 31; i >= 0; i--) {
if (isBitSet(x, i))
return i;
}
return -1;
}

public static int findRightMostUnsetBit(int x) {
for (int i = 0; i <= 31; i++) {
if (! isBitSet(x, i))
return i;
}
return -1;
}

public static int findLeftMostUnsetBit(int x) {
int k = findLeftMostSetBit(x);
for (int i = k; i >= 0; i--) {
if (! isBitSet(x, i))
return i;
}
return -1;
}

public static1+ void main(String[] args) {
int x =
(1 << 0) |
(1 << 1) |
(1 << 4) |
(1 << 5) |
(1 << 6) |
(1 << 8);
System.out.println(findLeftMostUnsetBit(x));
System.out.println(findRightMostUnsetBit(x));
}

}

如果我没记错的话,我当前的实现需要线性时间。我们可以做得更好吗?

最佳答案

下面是 Integer.numberOfLeadingZeros 的源代码。正如所指出的那样,它取自 HD(Henry S. Warren, Jr 的 Hacker's Delight)

主要思想是使用二进制搜索而不是逐位迭代。如果您对 bit twiddling 感兴趣,请查看这本书。这是一件美妙的艺术品。

public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}

关于java - 在 Java 中查找最左/最右未设置位的索引的最有效方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6495685/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com