在 Java 中，如何以整数的反转二进制形式获取 1 的位置？

Question

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

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

在没有 String 操作的现代 Java 中，有什么简洁明了的方法来实现这一点？与 String 的转换对我来说似乎很浪费，而且我知道String.reverse()无论如何都没有简单的方法来翻转 String (no )。

Answer 1

只需依次检查位：

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;
}

在线演示

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

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

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

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;
}

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

1. 单个内存分配，Integer.bitCount用于ArrayList预先适当调整大小。
2. 最小循环迭代次数，每组位^{1 一次}。

内部循环相当简单：

• Integer.lowestOneBitint仅返回输入集的最低位。
• input - one 从输入中“取消设置”这一位，用于下一次迭代。
• Integer.numberOfTrailingZeros 以二进制形式计算尾随零的数量，有效地为我们提供最低 1 位的索引。

¹ 值得注意的是，一旦编译，这可能不是最佳方式，相反，0..n基于的显式循环bitCount将更容易为 JIT 展开。

Answer 4

由于您编写了“现代 Java”，因此可以使用流（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 5

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

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 6

一个愚蠢的答案，只是为了多样性：

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 7

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

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 8

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

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 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

@Matthieu M. 的流版本回答：

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

Answer 11

您可以使用此解决方案：

    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 12

或者如果你想要：

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 13

只需使用indexOfString类的功能

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);
        }
    }
}