7
\$\begingroup\$

I've been practicing using recursion lately and thought this was a case where it would prove really useful, is this good use or is there some superior non-recursive way to go about it?

Challenge:

Write a program which determines the number of 1 bits in the internal representation of a given integer.

Specifications:

The first argument is a path to a file.
The file contains integers, one per line.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BinaryOnes {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            printBinaryOnesCount(input.nextLine());
        }
    }

    private static void printBinaryOnesCount(String line) {
        System.out.println(binaryOnesCount(Integer.parseInt(line)));
    }

    private static int binaryOnesCount(int n) {
        if (n < 2) { return n; }
        return binaryOnesCount(n / 2) + n % 2;
    }
}

Sample Input:

10
22
56

Sample Output:

2
3
3

\$\endgroup\$
8
\$\begingroup\$

Your code's general structure is decent. The Single-Responsibility-Principle is established by having relatively clear logic structures in the main, print* and binaryOnesCount methods. While the basic structure is fine, the actual bitcount algorithm is very inefficient.

Recursion is not the answer to this problem.

Even if recurstion was the solution, I don't like how you find the low bit, and I don't like your terminal conditions. Additionally, actual bitwise operations should be used to count actual bits.

Additionally, your continued use of 1-liners for conditional blocks is disheartening.

So, if you have to use recursion, something like:

private static int binaryOnesCount(int n) {
    // clear terminal block.
    if (n == 0) {
        return 0;
    }

    int lowbit = n & 1; // is the low bit set.

    // Use an unsigned right-shift to strip the low bit.
    return lowbit + binaryOnesCount( n >>> 1);

}

But, Recursion is not the answer. It has an expensive overhead in the stack.

A simpler solution is:

private static int binaryOnesCount(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;
}

Of course, this is all reinventing the wheel.... There's a really cool bitwise implementaton using fancy masks and shifts, that can do it really fast. It's already implemented in: Integer.bitCount(int)

See Source code (HD is Hacker's Delight book):

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}
\$\endgroup\$
  • \$\begingroup\$ Not at all familiar with the bit-wise stuff. Didn't realize there already was a built in method. Haha, and I felt so good when I came up with this solution. Thanks for the enlightenment. What's wrong with using 1 liners? \$\endgroup\$ – Legato Feb 3 '15 at 16:20
  • \$\begingroup\$ @Legato 1 liners are hard to read most of the time, since it's compacting everything. \$\endgroup\$ – Marc-Andre Feb 3 '15 at 16:29
  • \$\begingroup\$ Even in this case? I tend to use it if it's short and only a single effect, should I just altogether forego using them? \$\endgroup\$ – Legato Feb 3 '15 at 16:31
  • \$\begingroup\$ By Java code convention you should not use one liners. See 7.4 in oracle.com/technetwork/java/javase/documentation/… \$\endgroup\$ – barq Feb 3 '15 at 16:48
  • \$\begingroup\$ Regarding the library method: more importantly, it can be JITed to POPCNT, a single x86 instruction. \$\endgroup\$ – wchargin Feb 3 '15 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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