Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

574
Visualizações
In Java, how to get positions of ones in reversed binary form of an integer?

I have a legacy application that takes an integer, converts it to a binary string, reverses that string, and then gets the positions of bits (ones) as a list of integers. For example:

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

What is a succinct and clear way to accomplish this in modern Java without the String operations? The conversion to and from String seems wasteful to me, and I know there's no simple way to flip a String (no String.reverse()) anyway.

over 4 years ago · Santiago Trujillo
13 Respostas
Responde à pergunta

0

You don't need to reverse the actual binary string. You can just calculate the index.

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);
}
over 4 years ago · Santiago Trujillo Relatório

0

You can just test the bits without turning the integer into a string:

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

Bits are usually counted from right to left, the rightmost bit being bit 0. The operation 1 << bit gives you an int whose bit numbered bit is set to 1 (and the rest to 0). Then use & (binary and) to check if this bit is set in the input, and if so, record the position in the output array.

over 4 years ago · Santiago Trujillo Relatório

0

Just check the bits in turn:

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]
over 4 years ago · Santiago Trujillo Relatório

0

Just use the indexOf function of the String 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);
        }
    }
}
over 4 years ago · Santiago Trujillo Relatório

0

You can use this solution:

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

It outputs:

[2, 3]
[1, 2, 3]
[4]
over 4 years ago · Santiago Trujillo Relatório

0

I would definitely prefer Andy's answer myself, even if it seems cryptic at first. But since no one here has an answer with streams yet (even if they are totally out of place here):

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());
}
over 4 years ago · Santiago Trujillo Relatório

0

Since you wrote "modern Java", this is how it can be done with streams (Java 8 or better):

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

The map is only needed since you start counting at 1 and not at 0.

Then

System.out.println(digits);

prints

[1, 2, 3]
over 4 years ago · Santiago Trujillo Relatório

0

A silly answer, just for variety:

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

(Thanks to pero_hero for pointing out the masking was necessary on WJS's answer)

over 4 years ago · Santiago Trujillo Relatório

0

just for fun:

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);
over 4 years ago · Santiago Trujillo Relatório

0

Given the original integer returns a list with the bit positions.

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

Or if you want to do bit shifting.

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;

}

over 4 years ago · Santiago Trujillo Relatório

0

or if you want:

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());
over 4 years ago · Santiago Trujillo Relatório

0

May I propose a pure bit-wise solution?

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

This solution is algorithmically optimal:

  1. Single memory allocation, using Integer.bitCount to appropriately size the ArrayList in advance.
  2. Minimum number of loop iterations, one per set bit1.

The inner loop is rather simple:

  • Integer.lowestOneBit returns an int with only the lowest bit of the input set.
  • input - one "unset" this bit from the input, for next iteration.
  • Integer.numberOfTrailingZeros count the number of trailing zeros, in binary, effectively giving us the index of the lowest 1 bit.

1 It is notable that this may not be the most optimal way once compiled, and that instead an explicit 0..n loop based on the bitCount would be easier to unroll for the JIT.

over 4 years ago · Santiago Trujillo Relatório

0

a stream version of @Matthieu M. answer:

 List<Integer> list = IntStream.iterate(value, (v) -> v != 0, (v) -> v & (v - 1))
                .mapToObj(val -> Integer.numberOfTrailingZeros(val) + 1)
                .collect(toList());
over 4 years ago · Santiago Trujillo Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda