{{announcement.body}}
{{announcement.title}}

42: The Answer To Life, The Universe and Everything

DZone 's Guide to

42: The Answer To Life, The Universe and Everything

Take a deep dive into the inner-working of JDK's bitCount method to answer the all-important question, that Java hitchhikers have been asking for millennia.

· Java Zone ·
Free Resource

The story started with a Twitter Post about the JDK method bitCount which is available for Long and Integer types.

If you take a look into the time line, there was a reply by @ScottSelikoff (funny comment of course) who stated 42 as the answer to life, the universe and everything to the magic method which has been followed by Lukas Eder:

For what percentage of longs would that be the correct result?

This thread has inspired me to this article.

So let us summarize that question:


For what percentage of long values is bitCount() == 42?

The first question which arises: What does bitCount do? Let us take a look into the java doc of the function (Integer variant):

Returns the number of one-bits in the two's complement binary representation of the specified int value. This function is sometimes referred to as the population count.

So in the end bitCount counts the number (as the name implies) of 1s which are in a given value.

Here are some exemplary values for the type Integer:

  • Integer i = 0b1100_0000_0000_0000_0000_0000_0000_0000bitCount=2
  • Integer i = 0b0000_0000_0000_0000_0000_0000_0000_0011bitCount=2
  • Integer i = 0b0000_0000_0000_0000_0000_0000_0000_1111bitCount=4
  • Integer i = 0b1111_1111_1111_0000_0000_0000_0000_0000bitCount=12
  • Integer i = 0b1010_1010_1010_1010_1010_1010_0000_0000bitCount=12
  • Integer i = 0b1111_1111_1111_1111_1111_1111_1111_1111bitCount=32

A very naive way of trying to solve that question would be to write code like this:

Java


The first line will create 2^64 which is equal to 100% and the BigDecimal.valueOf(v).divide(pow).multiply(BigDecimal.valueOf(100L)) will just calculate the percentage of the value (number of values for appropriate bit count) of the resulting map which contains the number.

Ok now we can try that.... Really? Never. This code will run a very very long time...

A long time ago in a galaxy far, far away...

That might be a little long to wait for the result. Ok let's think a bit about the code. Ah! Yes of course I got it. We should use parallel() for the stream to get it faster.

Java


That version will be faster than the previous one and will take... Sorry but I simply don't know cause I have not tested it ;-).

Can we make a simpler and faster solution to get a result in the end?  Ok we change the Long into Integer? Now the code looks like this. As you see I already added the parallel() in the code to get faster also you see I'm using BigDecimal.valueOf(2L).pow(32) (2^32) instead of 2^64 based on the usage of Integer

Java


So this code will run in ca. 15 seconds (Hexa Core CPU's) with the following result:

Plain Text


The first column k= is the bitCount so the first line means: 

We have a single value v=1 where the bitCount==0 and 0.000 percent.  

Let use take a value on the line for  k=16 and v=601,080,390 and 13,995 percent of the values of Integer. So it means for bitCount=16 we have 601,080,390 values which are 13,995 percent of all integer values.

One interesting observation which can be made here is that the number of values is rising up to a maximum value at k=16 (bitCount=16) which you might not have expected. Another thing is that the number of values is going down to the higher number with bitCount=32 etc. 

Based on the runtime of this example you could roughly estimate the runtime for the variant with Long: 15 s * 2^32 = 64.424.509.440 seconds / 86400 seconds / day =  745.654 days / 365 days / year which results in ca. 2,000 years. So having a machine which has 1000 times more CPUs it could be dropped down to about 2 years (theoretically) or maybe you could use more power by using GPU's on AWS cloud but in the end no realizable solution.

So we need to reconsider if there is a faster or easier solution to answer the question? Yes there is one.
The answer can be found by using some mathematics.

Let us take a known example from the above result output:
We have 32 bits (Integer). Now we have 16 bits which should be 0 and 16 bits which should be 1. By expressing that like this:

Plain Text


You can calculate that via WolframAlpha and the result is: 601080390 which is exact the number in the above example. Let us check some other values:

Plain Text


The resulting value will be two times in the table one for k=9 (bitCount=9) and for k=23 (bitCount=23). The bitCount=9 means 9 - 1s (and 23 - 0s) are in the integer value and bitCount=23 means 23 - 1 s (and 9 - 0) are in the integer values.

So based on the mathematics we could really answer the question via:

Plain Text


So this means we have 80,347,448,443,237,920 numbers where the bitCount=42 and this means

Plain Text


So 0,435 percent of all long values having a bitCount=42.

Topics:
java, jdk, programming

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}