我怎样才能得到位的位置

Question

我有一个十进制数，我需要将其转换为二进制，然后找到一个在该二进制表示中的位置。

输入为 5，其二进制为 101，输出应为

1
3

下面是我的代码，它只提供 2 的输出，而不是我想提供一个二进制表示的位置。我怎样才能获得从 1 开始的设置位的位置？

public static void main(String args[]) throws Exception {
    System.out.println(countBits(5));
}

private static int countBits(int number) {
    boolean flag = false;

    if (number < 0) {
        flag = true;
        number = ~number;
    }
    int result = 0;
    while (number != 0) {
        result += number & 1;
        number = number >> 1;
    }
    return flag ? (32 - result) : result;
}

Answer 1

您需要跟踪您所处的位置，当 number & 1 结果为 1 时，打印出该位置。它看起来像：

...
int position = 1;
while (number != 0) {
    if((number & 1)==1)
        System.out.println(position);
    result += number & 1;
    position += 1;
    number = number >> 1;
}
...

Answer 2

有一种方法可以使用按位运算来解决您的问题。
Integer.toBinaryString(int number) 将整数转换为由零和一组成的字符串。这对您来说很方便，因为您可以改为：

public static void main(String args[]) throws Exception {
    countBits(5);
}

public static void countBits(int x) {
  String binaryStr = Integer.toBinaryString(x);
  int length = binaryStr.length();
  for(int i=0; i<length; i++) {
    if(binaryStr.charAt(i)=='1')
      System.out.println(length-1);
  }
}

它绕过了您可能想做的事情（在 Java 中学习按位运算），但在我看来它使代码看起来更清晰。

Answer 3

二进制表示：你的数字，就像现代（非量子）计算机上的任何东西一样，已经是内存中的二进制表示，作为给定的位序列尺寸。

位运算 您可以使用移位、位掩码、'AND'、'OR'、'NOT' 和 'XOR' bitwise operations 来操作它们并在个人级别上获取有关它们的信息位。

你的例子

对于您的示例编号 5 (101)，您提到您的预期输出为 1, 3。这有点奇怪，因为一般来说一个人会从 0 开始计数，例如对于 5 作为 byte（8 位数）：

     76543210  <-- bit index
5    00000101

所以我希望输出为 0 和 2 因为这些位索引处的位已设置 (1).

您的示例实现显示了函数

的代码

private static int countBits(int number)

它的名称和签名暗示了任何实现的以下行为：

它采用整数值 number 和 returns 单个输出值。
目的是计算输入number中设置了多少位。

即它与您描述的预期功能完全不匹配。

一个解决方案

您可以结合使用 'bit shift' (>>) 和 AND (&) 运算来解决您的问题。

int index = 0; // start at bit index 0

while (inputNumber != 0) { // If the number is 0, no bits are set

    // check if the bit at the current index 0 is set
    if ((inputNumber & 1) == 1)         
        System.out.println(index);  // it is, print its bit index.

    // advance to the next bit position to check
    inputNumber = inputNumber >> 1; // shift all bits one position to the right
    index = index + 1;              // so we are now looking at the next index.
}

如果我们运行为您的示例输入数字“5”，我们将看到以下内容：

iteration   input  76543210     index    result
1           5      00000101     0        1 => bit set.
2           2      00000010     1        0 => bit not set.
3           1      00000001     2        1 => bit set.
4           0      00000000     3        Stop, because inputNumber is 0

Answer 4

您的想法是让 countBits return 结果，而不是将 System.out.println 放入方法中，这通常是最好的方法。如果你想要它 return 一个位位置列表，类似的是让你的方法 return 一个数组或某种列表，比如：

private static List<Integer> bitPositions(int number) {

正如我在评论中提到的，如果您使用 >>> 并摆脱检查负片的特殊代码，您的生活将会轻松很多。这样做，并调整你已有的代码，会给你类似

的东西

private static List<Integer> bitPositions(int number) {
    List<Integer> positions = new ArrayList<>();
    int position = 1;
    while (number != 0) {
        if (number & 1 != 0) {
            positions.add(position);
        }
        position++;
        number = number >>> 1;
    }
    return positions;
}

现在调用者可以随心所欲地打印位置了。如果你在上面使用 System.out.println，输出将是 [1, 3]。如果您希望每个输出都在单独的行上：

for (Integer position : bitPositions(5)) {
     System.out.println(position);
}

在任何情况下，关于如何打印位置的决定（或者你想用它们做的任何其他事情）都与计算位置的逻辑分开，因为方法 return 是整个列出并且没有自己的 println.

（顺便说一下，正如 Alex 所说，最常见的是将低位视为 "bit 0" 而不是 "bit 1"，尽管我看过硬件手册称低位序位"bit 31"和高位"bit 0"，叫"bit 0"的好处是N位的1位代表值2^N，使事情变得简单。我的代码示例按照您在问题中的要求将其称为"bit 1"；但是如果您想将其更改为0，只需更改position的初始值即可。）

Answer 5

Integer.lowestOneBit 和 Integer.numberOfTrailingZeros 的组合立即给出最低 1-Bit 的位置，并且 returns 32 iff 数字为 0.

因此，下面的代码returns数数的1-Bits的位置按升序排列：

public static List<Integer> BitOccurencesAscending(int number)
{
    LinkedList<Integer> out = new LinkedList<>();
    int x = number;
    while(number>0)
    {
        x = Integer.lowestOneBit(number);
        number -= x;
        x = Integer.numberOfTrailingZeros(x);
        out.add(x);
    }
    return out;
}

我怎样才能得到位的位置

How can I get the position of bits

java

algorithm

binary

bit-manipulation