The number of non-zero quaternary (base 4) digits in a long?

Question

Let us start simple. Say you want to find how many 1's in a long in its binary representation. For example, how many 1's in 228₁₀? The binary represenation is 11100100₂. We can use Long.bitCount(228); which returns 4.

Now, let us say we will interpret two bits as a single quaternary digit (and the two far-right bits is the first digit):

00₂ = 0₄

01₂ = 1₄

10₂ = 2₄

11₂ = 3₄

Hence, 228₁₀ = 11100100₂ = 3210₄. The goal is to find how many non-zero quaternary digits are there in the binary representation. For examples, 3210₄ yields 3, 121100₄ yields 4, 000032₄ yields 2, etc.

The code of the Long.bitCount(i); method from Java's documentation is given by:

public static int bitCount(long i) {
    i = i - ((i >>> 1) & 0x5555555555555555L);
    i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
    i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    i = i + (i >>> 32);
    return (int)i & 0x7f;
}

The goal is to find how many non-zero quaternary digits are there in the binary representation without any types of loops nor the usage of Strings. I am trying to manipulate the code so that it works for quaternary. This is what I currently have:

public static int bitCountQuat(long i) {
    i = i - ((i >>> 2) & 0x3333333333333333L);
    i = (i & 0x3333333333333333L) + ((i >>> 4) & 0x0f0f0f0f0f0f0f0fL);
    i = (i + (i >>> 8)) & 0x00ff00ff00ff00ffL;
    i = i + (i >>> 16);
    i = i + (i >>> 32);
    i = i + (i >>> 64);
    return (int) i & 0x7f7f;
 }

For more reference: Efficient Implementation of Hamming Weight.

Here are the values from 0 to 9:

Binary, desired output, current output
0000,   0,  0
0001,   1,  2
0010,   1,  4
0011,   1,  6
0100,   1,  6
0101,   2,  0
0110,   2,  2
0111,   2,  4
1000,   1,  4
1001,   2,  6

user_2402272 · Answer

Start by converting all non-zero quaternary digits to 1s ...

i = (i & 0x5555555555555555L) | ((i >>  1) & 0x5555555555555555L));

... then count the bits in the result.

One way to do that bit count would be to continue from there with

i = (i & 0x3333333333333333L) + ((i >>  2) & 0x3333333333333333L));
i = (i & 0x0f0f0f0f0f0f0f0fL) + ((i >>  4) & 0x0f0f0f0f0f0f0f0fL));
i = (i & 0x00ff00ff00ff00ffL) + ((i >>  8) & 0x00ff00ff00ff00ffL));
i = (i & 0x0000ffff0000ffffL) + ((i >> 16) & 0x0000ffff0000ffffL));
i = (i & 0x00000000ffffffffL) +  (i >> 32);

, which are the trailing steps of the implementation presented in the Wikipedia article you referenced.

Alternatively, you could use the (whole) implementation of Long.bitCount(), or even Long.bitCount() itself for the bit counting part. Its variation has enough fewer operations than the (full) Wikipedia version to be about a wash with the above shortcut version.

The number of non-zero quaternary (base 4) digits in a long?

1 Answers