在Java中，如何获取一个整数的倒二进制形式的位置？

Question

我有一个遗留应用程序，它接受一个整数，将其转换为二进制字符串，反转该字符串，然后获取位（个）的位置作为整数列表。例如：

6 -> "110" -> "011" -> (2,3) 
7 -> "111" -> "111" -> (1,2,3)
8 -> "1000" -> "0001" -> (4)

在现代 Java 中没有字符串操作的情况下，有什么简洁明了的方法可以完成此操作？与 String 之间的转换对我来说似乎很浪费，而且我知道无论如何都没有简单的方法来翻转 String（没有 String.reverse()）。

Answer 1

您不需要反转实际的二进制字符串。你可以计算指数。

String str = Integer.toBinaryString(num);
int len = str.length();
List<Integer> list = new ArrayList<>();
for (int i=0; i < len; i ++) {
  if (str.charAt(i) == '1') list.add(len - 1 - i);
}

Answer 2

您可以只测试位，而无需将整数转换为字符串：

List<Integer> onePositions(int input) {
  List<Integer> onePositions = new ArrayList<>();
  for (int bit = 0; bit < 32; bit++) {
    if (input & (1 << bit) != 0) {
      onePositions.add(bit + 1); // One-based, for better or worse.
    }
  }
  return onePositions;
}

位通常从右到左计数，最右边的位是位 0。操作 1 << bit 得到一个 int，其编号为 bit 的位被设置为 1（并且其余为 0）。然后使用&（二进制与）检查input中是否设置了这个位，如果是，则记录输出数组中的位置。

Answer 3

只需依次检查位：

List<Integer> bits(int num) {
  List<Integer> setBits = new ArrayList<>();
  for (int i = 1; num != 0; ++i, num >>>= 1) {
    if ((num & 1) != 0) setBits.add(i);
  }
  return setBits;
}

Online Demo

6 [2, 3]
7 [1, 2, 3]
8 [4]

Answer 4

只需使用String的indexOf函数class

public class TestPosition {
    public static void main(String[] args) {
        String word = "110"; // your string
        String guess = "1"; // since we are looking for 1
        int totalLength = word.length();
        int index = word.indexOf(guess);
        while (index >= 0) {
            System.out.println(totalLength - index);
            index = word.indexOf(guess, index + 1);
        }
    }
}

Answer 5

您可以使用这个解决方案：

    static List<Integer> convert(int input) {
        List<Integer> list = new ArrayList<>();
        int counter = 1;
        int num = (input >= 0) ? input : Integer.MAX_VALUE + input + 1;
        while (num > 0) {
            if (num % 2 != 0) {
                list.add(counter);
            }
            ++counter;
            num /= 2;
        }
        return list;
    }

它输出：

[2, 3]
[1, 2, 3]
[4]

Answer 6

我肯定更喜欢安迪自己的回答，即使一开始看起来很神秘。但是由于这里还没有人对流有答案（即使它们在这里完全不合适）：

public List<Integer>  getList(int x) {
    String str = Integer.toBinaryString(x);
    final String reversed = new StringBuilder(str).reverse().toString();
    return IntStream.range(1, str.length()+1)
            .filter(i -> reversed.charAt(i-1)=='1')
            .boxed()
            .collect(Collectors.toList());
}

Answer 7

自从您编写了 "modern Java"，这就是使用 streams（Java 8 或更高）可以完成的方式：

final int num = 7;

List<Integer> digits = IntStream.range(0,31).filter(i-> ((num & 1<<i) != 0))
        .map(i -> i+1).boxed().collect(Collectors.toList());

只有在您从 1 而不是 0 开始计数时才需要地图。

然后

System.out.println(digits);

打印

[1, 2, 3]

Answer 8

愚蠢的回答，只是为了多样性：

BitSet bs = BitSet.valueOf(new long[] {0xFFFFFFFFL & input});
List<Integer> setBits = new ArrayList<>();
for (int next = -1; (next = bs.nextSetBit(next + 1)) != -1;) {
  setBits.add(next + 1);
}

（感谢 pero_hero 指出 WJS 的回答需要屏蔽）

Answer 9

纯属娱乐：

Pattern one = Pattern.compile("1");
List<Integer> collect = one.matcher(
             new StringBuilder(Integer.toBinaryString(value)).reverse())
            .results()
            .map(m -> m.start() + 1)
            .collect(Collectors.toList());
System.out.println(collect);

Answer 10

给定原始整数 returns 一个包含位位置的列表。

static List<Integer> bitPositions(int v) {
     return BitSet.valueOf(new long[]{v&0xFF_FF_FF_FFL})
                .stream()
                .mapToObj(b->b+1)
                .collect(Collectors.toList());
}

或者如果你想进行位移。

static List<Integer> bitPositions(int v ) {
    List<Integer> bits  = new ArrayList<>();
    int pos = 1;
    while (v != 0) {
        if ((v & 1) == 1) {
            bits.add(pos);
        }
        pos++;
        v >>>= 1;
    }
    return bits;

}

Answer 11

或者如果你想：

String strValue = Integer.toBinaryString(value);
List<Integer> collect2 = strValue.codePoints()
           .collect(ArrayList<Integer>::new,
                   (l, v) -> l.add(v == '1' ? strValue.length() - l.size() : -1), 
                   (l1, l2) -> l1.addAll(l2)).stream()
           .filter(e -> e >= 0)
           .sorted()
           .collect(toList());

Answer 12

我可以提出一个纯粹的按位解决方案吗？

static List<Integer> onesPositions(int input)
{
    List<Integer> result = new ArrayList<Integer>(Integer.bitCount(input));

    while (input != 0)
    {
        int one = Integer.lowestOneBit(input);
        input = input - one;
        result.add(Integer.numberOfTrailingZeros(one));
    }

    return result;
}

这个解决方案在算法上是最优的：

单一内存分配，使用Integer.bitCount预先适当调整ArrayList大小。
最小循环迭代次数，每组一个bit¹.

内部循环相当简单：

Integer.lowestOneBit returns 一个 int 只有输入集的最低位。
input - one "unset" 来自输入的这个位，用于下一次迭代。
Integer.numberOfTrailingZeros 以二进制计算尾随零的数量，有效地为我们提供了最低 1 位的索引。

¹ 值得注意的是，这可能不是编译后的最佳方式，而是一个基于 0..n 的显式循环bitCount 对于 JIT 会更容易展开。

Answer 13

@Matthieu M 的流媒体版本。回答：

 List<Integer> list = IntStream.iterate(value, (v) -> v != 0, (v) -> v & (v - 1))
                .mapToObj(val -> Integer.numberOfTrailingZeros(val) + 1)
                .collect(toList());

在Java中，如何获取一个整数的倒二进制形式的位置？

In Java, how to get positions of ones in reversed binary form of an integer?

java

binary

bit-manipulation