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.
But we can use BCD conversion to convert the integer to BCD and then reverse using shift operators. So after BCD conversion we can shift every set of 4 bits (representing a digit ranging from 0-9) step wise in the opposite order, to get the reversed Number in BCD format.
Bitwise complement operator is used to reverse the bits of an expression.
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]
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.
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:
Integer.bitCount
to appropriately size the ArrayList
in advance.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.1It 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.
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]
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());
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With