In Java, how to get positions of ones in reversed binary form of an integer?
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;}
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:
- Single memory allocation, using
Integer.bitCount
to appropriately size theArrayList
in advance. - Minimum number of loop iterations, one per set bit1.
The inner loop is rather simple:
Integer.lowestOneBit
returns anint
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.