Hacker News Reader

Comment by tombert | Hacker News Reader

I started using LMAX Disruptor for some projects. One quirk with Disruptor is that the queue size always has to be an exponent of two.

I wanted to make sure that I always have at least enough room for any size and I didn't want to manually compute, so I wrote this:

    var actualSize = Double.valueOf(Math.pow(2,  Math.ceil(Math.log(approxSize) / Math.log(2)))).intValue();

A bit much for a single line, but just using some basic log rules in order to the correct exponent. I learned all this in high school, but some of my coworkers thought I was using this amazing, arcane bit of math that had never been seen before. I guess they never use log outside of Big-O notation.

View on HN

This is perfectly usable, of course, but I’d write

  var actualSize = Integer.highestOneBit(approxSize - 1) << 1;

purely to avoid involving the horrors that live beneath the humble pow() and log().

(Integer.highestOneBit, also known as “isolate leftmost bit”, “most significant one”, or the like, essentially has to be a primitive to be efficient, unlike its counterpart for the lowest bit, x&-x. The actual CPU instruction is usually closer to Integer.numberOfLeadingZeros, but that’s just a bitshift away.)

That's pretty cool; I didn't even consider doing any cool bitwise arithmetic.

I didn't particularly care about performance or anything for this particular case, since it runs exactly once at the start of the app just to initiate the Disruptor.

shouldn't it be

var actualSize = 1 << Integer.highestOneBit(approxSize - 1);

Nope. I don’t know why the Java folks decided not to use the fairly standard verb “isolate” for this method, but that’s what it is[1]:

> public static int highestOneBit(int i)

> Returns an int value with at most a single one-bit, in the position of the highest-order ("leftmost") one-bit in the specified int value. Returns zero if the specified value has no one-bits in its two's complement binary representation, that is, if it is equal to zero.

There isn’t a straight floor(log2(·)) as far as I can tell, only Integer.numberOfLeadingZeros, and turning the former into the latter is annoying enough[2] that I wouldn’t prefer it here.

[1] https://docs.oracle.com/javase/8/docs/api/java/lang/Integer....

[2] https://docs.oracle.com/javase/8/docs/api/java/lang/Integer....

Thanks. What a weird API.

The above gives an incorrect result for approxSize = 1 (namely 0). The following works (for values up to 2^30, of course):

    var actualSize = Integer.MIN_VALUE >>> Integer.numberOfLeadingZeros(approxSize - 1) - 1;

Or, if you want 0 to map to 0 instead of to 1:

    var actualSize = Integer.signum(approxSize) * Integer.MIN_VALUE >>> Integer.numberOfLeadingZeros(approxSize - 1) - 1;

Of course, you could also use a variation of:

    var actualSize = Math.min(1, Math.Integer.highestOneBit(approxSize - 1) << 1);

Just shift the size to the right 1 bit and count the shifts until the value turns to zero, and you'll get your number 2 exponent for the size :)

Reply on news.ycombinator.com