1
\$\begingroup\$

I want to count the number of bits set to 0 at the beginning of a byte array. So far the code I have is this:

    public static int getPrefixLength(byte[] bytes) {

        int prefixLength = 0;

        for (byte b : bytes) {
            if (b == 0) {
                prefixLength += 8; // 1 byte = 8 bits
            } else {
                int tmp = 0;
                for (int i = 7; i >= 0; i--) {
                    if ((b & (1 << i)) == 0) {
                        tmp++;
                    } else {
                        break;
                    }
                }
                prefixLength += tmp;
            }
        }

        return prefixLength;
    }

How can I improve this?

\$\endgroup\$
5
  • \$\begingroup\$ How and why is this function called? \$\endgroup\$
    – Reinderien
    May 2, 2022 at 23:34
  • \$\begingroup\$ I have a Item class and each item has an ID which is a byte array. Then, I have a Item array and the index in which I store the item is the prefix length (e.g. if the prefix is 7 bits long, the item will be stored in the 7th index of the array) \$\endgroup\$
    – Pedro
    May 3, 2022 at 0:22
  • \$\begingroup\$ How wide is the ID? i.e., how many bytes are there? \$\endgroup\$
    – Reinderien
    May 3, 2022 at 0:23
  • \$\begingroup\$ 160 bits, 20 bytes \$\endgroup\$
    – Pedro
    May 3, 2022 at 1:26
  • 5
    \$\begingroup\$ Does this produce correct results? For example, for {0, 1, 0} it would return 23. Is that what is wanted? Or should it return 15? \$\endgroup\$
    – mdfst13
    May 3, 2022 at 1:29

4 Answers 4

1
\$\begingroup\$

Let's split it in two:

/**
 * Calculates the number of bits that are zero in the byte array from the left hand side.
 * The leftmost byte is the one with index zero, the leftmost bits in each byte are the most significant bits.
 * @param bytes the byte array containing bytes.length * Byte.SIZE bits
 * @return the number of leading zero bits 
 */
public static int numberOfLeadingZeroBits(byte[] bytes) {
    int numberOfLeadingZeros = 0;
    for (byte b : bytes) {
        if (b == 0) {
            numberOfLeadingZeros += Byte.SIZE;
        } else {
            return numberOfLeadingZeros + numberOfLeadingZeroBits(b);
        }
    }
    return numberOfLeadingZeros;
}

// TODO similar API description in JavaDoc    
public static int numberOfLeadingZeroBits(byte b) {
    for (int i = Byte.SIZE - 1; i >= 0; i--) {
        if (((b >> i) & 1) == 1) {
            return Byte.SIZE - 1 - i;
        }
    }
    return Byte.SIZE;
}

Note that we can immediately return once we have the number of zero bits of the byte - as obviously we would have to stop execution.

I've renamed the methods as getPrefixLength doesn't indicate to the user what the prefix is supposed to be.

Just for fun I moved the bit in byte b instead of performing a mask. It really doesn't matter much, but sometimes it is fun to see some alternatives.

If performance is an issue it is possible to inline the second method - but I would strongly prefer not to.


Furthermore, you could do a one-liner, which - mind you - will perform a copy of the entire byte array:

int numberOfLeadingZeroBits = bytes.length * Byte.SIZE - new BigInteger(1, bytes).bitLength();

I always use Byte.SIZE instead of e.g. 8, because it greatly clarifies what the number represents in the code. It might be slightly faster to create a local private static final int BITS_IN_BYTE = 8 value, if speed is a concern.

\$\endgroup\$
0
\$\begingroup\$

If your representation allows for it, iterating over 64-bit longs packing 8 bytes each will be faster than iterating per byte. If you need to convert to this representation from your byte array (perhaps using ByteBuffer), the conversion cost may outweigh any performance benefit. Measure this for your specific scenario. Since your ID array is actually 20 bytes, even having 5x 32-bit integers or a mix of int and long could work.

Replace your inner bit-twiddling loop with a call to the built-in numberOfLeadingZeros. This will be simple and fast. If you absolutely need to sacrifice legibility and simplicity in the name of speed, there are faster, more complicated methods.

In my tests, there is a slight performance improvement to using numberOfLeadingZeros; its biggest benefit is simplicity. Packing is much more effectual in reducing execution time. If I had to pick a favourite, it would be the 5x 32-bit int version for its uniformity of representation and execution efficiency.

Timing fixture

import java.nio.ByteBuffer;
import java.nio.IntBuffer;
import java.util.Arrays;
import java.util.HexFormat;

import java.util.List;
import java.util.HashMap;
import java.util.Map;

import static java.lang.System.nanoTime;
import static java.lang.System.out;

public class Main {
    private static final IdParser[] parsers = {
        new IntLongParser(),
        new BuiltinIntParser(),
        new BuiltinBytesParser(),
        new OldBytesParser(),
    };

    private static abstract class IdParser {
        private static final HexFormat format = HexFormat.of();

        public ID parse(String str) {
            ByteBuffer buf = ByteBuffer.wrap(format.parseHex(str));
            return construct(buf);
        }

        protected abstract ID construct(ByteBuffer buf);
    }

    private static class OldBytesParser extends IdParser {
        protected ID construct(ByteBuffer buf) {
            return new OldBytesID(buf.array());
        }
    }

    private static class BuiltinBytesParser extends IdParser {
        protected ID construct(ByteBuffer buf) {
            return new BuiltinBytesID(buf.array());
        }
    }

    private static class BuiltinIntParser extends IdParser {
        protected ID construct(ByteBuffer buf) {
            IntBuffer ibuf = buf.asIntBuffer();
            int[] array = new int[ibuf.capacity()];
            ibuf.get(array);
            return new BuiltinIntID(array);
        }
    }

    private static class IntLongParser extends IdParser {
        protected ID construct(ByteBuffer buf) {
            IntLongID id = new IntLongID(
                buf.getLong(),
                buf.getLong(),
                buf.getInt()
            );
            if (buf.hasRemaining())
                throw new RuntimeException("Unexpected data while parsing ID");
            return id;
        }
    }

    private static abstract class ID {
        public abstract int prefixLen();
    }

    private static class OldBytesID extends ID {
        private final byte[] id;
        public OldBytesID(byte[] id) { this.id = id; }

        public int prefixLen() {
            int prefixLength = 0;

            for (byte b: id) {
                if (b == 0) {
                    prefixLength += 8; // 1 byte = 8 bits
                } else {
                    int tmp = 0;
                    for (int i = 7; i >= 0; i--) {
                        if ((b & (1 << i)) == 0) {
                            tmp++;
                        } else {
                            break;
                        }
                    }
                    prefixLength += tmp;
                }
            }

            return prefixLength;
        }
    }

    private static class BuiltinBytesID extends ID {
        private final byte[] id;
        public BuiltinBytesID(byte[] id) { this.id = id; }

        public int prefixLen() {
            int prefix = 0;

            for (byte b: id) {
                if (b == 0)
                    prefix += 8;
                else
                    return prefix + Integer.numberOfLeadingZeros(b << 24);
            }

            return prefix;
        }
    }

    private static class BuiltinIntID extends ID {
        private final int[] id;
        public BuiltinIntID(int[] id) { this.id = id; }

        public int prefixLen() {
            int prefix = 0;

            for (int i: id) {
                if (i == 0)
                    prefix += 32;
                else
                    return prefix + Integer.numberOfLeadingZeros(i);
            }

            return prefix;
        }
    }

    private static class IntLongID extends ID {
        private final long l1, l2;
        private final int i3;
        public IntLongID(long l1, long l2, int i3) {
            this.l1 = l1; this.l2 = l2; this.i3 = i3;
        }

        public int prefixLen() {
            if (l1 != 0)
                return Long.numberOfLeadingZeros(l1);
            if (l2 != 0)
                return Long.numberOfLeadingZeros(l2) + 64;
            return Integer.numberOfLeadingZeros(i3) + 128;
        }
    }

    public static void main(String[] args) {
        List<ID> ids = Arrays.stream(parsers)
            .map(p -> p.parse(args[0]))
            .toList();

        // We need to stripe the time trials, because the first few iterations are
        // slower while the CPU spins up and/or the OS thread scheduler allocates
        // more time.
        final int stripeSize = 1_000, iterations = 10_000;

        Map<String, Double> times = new HashMap<>();
        for (ID id: ids)
            times.put(id.getClass().getSimpleName(), 0d);

        // Save (even though we overwrite) the prefix results, to prevent the
        // inner operation from being optimised away.
        Map<String, Long> prefixes = new HashMap<>();

        for (int i = 0; i < iterations; i++) {
            for (ID id: ids) {
                String name = id.getClass().getSimpleName();
                Result result = timePrefix(id, stripeSize);
                times.put(name, times.get(name) + result.time);
                prefixes.put(name, result.prefix);
            }
        }

        for (Map.Entry<String, Long> kv: prefixes.entrySet()) {
            out.printf(
                "%20s: prefix=%d time=%.1f ns%n",
                kv.getKey(), kv.getValue(),
                times.get(kv.getKey()) / iterations);
        }
    }

    private record Result(long prefix, double time) { }

    private static Result timePrefix(ID id, int stripeSize) {
        long prefix = 0;

        long start = nanoTime();
        for (int i = 0; i < stripeSize; i++)
            prefix += id.prefixLen();
        double dur = ((double)(nanoTime() - start))/stripeSize;

        return new Result(prefix/stripeSize, dur);
    }
}

Output

When this is passed:

0000000000000000000000000000000000000002

i.e. an almost-worst-case two bits short of being empty, we get:

           IntLongID: prefix=158 time=13.4 ns
        BuiltinIntID: prefix=158 time=19.4 ns
      BuiltinBytesID: prefix=158 time=37.1 ns
          OldBytesID: prefix=158 time=39.4 ns
\$\endgroup\$
0
\$\begingroup\$

You can get rid of the else blocks by using some simple transformations

Outer if

  • You can use continue to get rid of else if
for (byte inputByte : bytes) {
    if (inputByte == 0) {
        prefixLength += 8;
        continue;
    }

    for (int i = 7; i >= 0; i--) {
    ...
    }

}

Inner if

  • You can invert the if statement and call the break there
for (int bitShifter = 7; bitShifter >= 0; bitShifter--) {
    if ((inputByte & (1 << bitShifter)) != 0) {
        break;
    }
    prefixLength++;
}

All together

int prefixLength = 0;

for (byte inputByte : bytes) {
    if (inputByte == 0) {
        prefixLength += 8;
        continue;
    }

    for (int bitShifter = 7; bitShifter >= 0; bitShifter--) {
        if ((inputByte & (1 << bitShifter)) != 0) {
            break;
        }
        prefixLength++;
    }
}

return prefixLength;
\$\endgroup\$
-1
\$\begingroup\$

The main problem with this code is that it doesn't solve the problem.

The code you've posted simply counts the number of 0 bits, which is not the same as counting the number of initial zero bits.

Make your code work, test that it works, and come back and ask for a second review.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ This isn't quite true either. It's true that it counts all the 0 bits in all the zero bytes. But in a non-zero byte, it only counts the initial bits. E.g. {0, 2, 0} returns 22 and {0, 64, 0} returns 17, even though there are 23 0 bits in both. Given the problem description, I think that it should return 14 and 9 respectively instead. But perhaps it is the problem description that is wrong, not the code. Or perhaps there is something about the input that keeps that from ever happening. E.g. {0, 2, -1} will return 14 as I would expect. \$\endgroup\$
    – mdfst13
    May 3, 2022 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.