给定一个数字（位序列）和一个位索引，我如何找到下一个最高位？

Question

如果我有一个输入，比如 51 (00110011) 和一个代表位索引的索引 i（例如 i = 0 -> 1，i = 2 -> 0），我如何找到 2 的幂像这些例子。抱歉，我不太擅长数学符号，但我可以提供示例输入和输出。

示例：如果给定 51 和索引 1 (00110011)，我想要一个函数 return 00010000 = 16.

此外，如果给定 173 和索引 2 (10101101)，函数必须 return 00001000 = 8.

我正在寻找一种解决方案，它最好根据数字的大小使用位运算而不使用循环。

编辑：这不是家庭作业。我正在编写一个程序，将用户 selections 存储为一个数字。我想在这里挑战自己。

这是我所能做的一点点

    x--;
    for (int j = 0; j < 5; j++) {
        x |= x >> (int) Math.pow(2, i);
    }
    x++;
    return x;

这需要一个 32 位数字和 returns 的下一个 2 的幂。我不确定这对我的问题是否有用。我试着看看是否有其他人发布了类似的内容，这就是我发现的，我认为它可能会影响我正在尝试做的事情。

编辑 2 我有用户一周中的 select 天，并将这些天存储在一个数字中。给定一天，我想找到用户在第二天 selected。我可以通过将数字转换为布尔数组来轻松做到这一点，但我想看看是否还有其他聪明的解决方案。如果太"homework"喜欢，我很抱歉。

我意识到如果我取像 51 (00110011) 这样的数字和索引 1，我可以通过除以 2^1 = 001100 来去掉前两位。然后，我希望程序找到位置第一个 1（索引 2）。那么它应该 return 2^(2+2) 因为它削减了 2 位并且下一个逻辑 1 在那之后位于索引 2 处。

Answer 1

无论如何你都必须使用循环。对于 java，对吧？代码：

public class Test {
    public static void main(String[] args) {
        System.out.println(yourHomework(51,1));
        System.out.println(yourHomework(173,2));
    }
    public static int yourHomework(int number, int index) { // LOL!! Joke!
            for (int i = index + 1; i < 32; i++) {
                if ((number | (1 << i)) == number)
                     return 1 << i;
            }
            return 0; // Or the value it must return if there is not answer
    }
}

这有帮助吗？。我用你的案例测试了它并且它有效，但我不确定这是否是你需要的。

Answer 2

也有非循环方式

有一些简单的技巧可以用最低的设置位来做事，例如将其设置为零或将其隔离。在这种情况下，我们将其设置为零：

int x = days & (days - 1);

这是可行的，因为减一会通过尾随零借位，直到到达最低设置位，它会重置该位，然后停止借位。

如果我们只需要隔离 x 中的最低设置位，也有一个简单的技巧：

int mask = x & -x;

之所以可行，是因为 -x 的另一种写法是 ~x + 1，这清楚地表明它将 "high bits" 翻转，但直到并包括最低集的部分x 中的位保持不变（它被翻转了，但随后 +1 将它全部翻转回来）。

在某些时候，我们可能还需要获取该位的索引。 Java 有 Integer.numberOfTrailingZeros，它有一个 Java 实现，比循环和一个一个地计算这些零更聪明，有些平台可能由本机指令实现（HotSpot可以做到这一点，但当然不一定每个平台上的每个 JVM 都可以或将会做到。

总之：

int pos = Integer.numberOfTrailingZeros(x); // note that we can use x here

给定一个数字（位序列）和一个位索引，我如何找到下一个最高位？

Given a number (bit sequence) and a bit index, how do I find the next highest order bit?

java

binary

bit-manipulation

bitwise-operators