I know I can write the following method to calculate the set bit indexes of a long :
private static List<Integer> bitPositions(long number) {
final List<Integer> positions = new ArrayList<>();
int position = 1;
while (number != 0) {
if ((number & 1L) != 0) {
positions.add(position);
}
position++;
number = number >>> 1;
}
return positions;
}
My question is : Is there a faster method to do this ?
On
If you don't mind using intrinsics, you can have an even faster version. Long.numberOfTrailingZeros() will use the CPU intrinsic that counts the number of consecutive zero bits starting from the least-significant bit (the BSF instruction on x86 processors).
For a sparse value, this will be faster than all other looping methods because it doesn't have any conditionals or branches within the main loop, it skips runs of any number of 0's with a single iteration, and, for a 64-bit long, the BSF intrinsic has a latency of only 3 clock cycles on Intel Haswell CPUs.
private static final byte[] bitPositions(long n) {
final byte[] result = new byte[Long.bitCount(n)];
byte bitPosition = 0;
for (int i = 0; n != 0L; i++) {
final byte bitsToSkip = (byte) (Long.numberOfTrailingZeros(n) + 1);
n >>>= bitsToSkip;
bitPosition += bitsToSkip;
result[i] = bitPosition;
}
return result;
}
Here I used a simple approach, sublinear time. You decide if you count from left or from right, in printf("%ld\n", 32-pos) you can consider 32-pos or pos.
bit_pos(unsigned long x)
{
unsigned long pos;
unsigned long w;
while(x) {
/* extract the rightmost `1` in `w` then remove it */
w = x&-x;
x-=w;
if (w) {
/* compute number of trailing zeros (location of 1) for w */
pos = 1;
if (!(w >> 16)) {pos+=16;w<<=16;}
if (!(w >> 24)) {pos+= 8;w<<= 8;}
if (!(w >> 28)) {pos+= 4;w<<= 4;}
if (!(w >> 30)) {pos+= 2;w<<= 2;}
pos = pos - (w >> 31);
printf("%ld\n", 32-pos);
}
}
printf("\n");
}
main()
{
bit_pos(2UL+4+32+1024);
bit_pos(3456789UL);
}
Fastest method
BitBank's answer to this question is about twice as fast as this answer's two methods just below this one. This steals the idea in BitBank's answer and makes it about 73% faster than it on my machine (9 times faster than the question's method) by using bit twiddling to repeatedly turn off the least-significant one bit rather than right-shifting the one bit off the right end and keeping track of how much shifting has occurred.
Improvements on BitBank's answer
bytespeeds things up slightly. I assume this is because it allows forbyte-sized rather thanint-sized arithmetic.Manual fusion
As Durandal pointed out in the question's comments, you can trade the following:
for a style that skips the method call and does this instead:
Benefits of fusion
Drawbacks of fusion
If you want to iterate multiple separate times through the bit positions of the same number, you have to compute the bit positions over again rather than reusing a previously generated array.
This might not be an actual drawback, though, if computing a bit position anew is quicker than loading a precomputed one from an array in RAM.
Slowest method
Here's a method that produces the same results (just in a
byte[]instead of aList<Integer>) about twice as fast:I'd recommend changing
byte bit = 1in theforloop tobyte bit = 0to switch to the traditional method of numbering bit positions starting with zero instead of one.Improvements
Long.bitCount(n)(uses the very speedy "popcount" instruction of your processor) speeds up your method quite a bit. You can change this by making theArrayListusingnew ArrayList<>(Long.bitCount(n)).ArrayList<Integer>is slower than abyte[], because:-127to128)Integervalues from theIntegercache to put them into theArrayList.ints stored in the resultingList<Integer>later on because you have to both retrieve theIntegerfrom theList<Integer>and then retrieve theintfrom theInteger.byte[]uses about 1/4th (32-bit system) or 1/8th (64-bit system) the memory of anArrayList<Integer>, sincebytes are that much smaller than pointers toIntegers.Slightly faster than slowest method, but uglier
As suggested by another person's deleted answer, loop unrolling speeds things up a little bit further on my machine (check whether that's true on your machine as well):
You can also change this to start counting the bit positions at zero instead of one.
Improvements
>>>on the number.++on the bit positon.