# An Army of Ones

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

• – rolfl Feb 3 '15 at 15:48
• There are a lot of good methods here: stackoverflow.com/questions/109023/… – barq Feb 3 '15 at 16:00
• binaryOnesCount(-5) will return -5. Is that what you wwant? – genisage Feb 3 '15 at 23:40

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.

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;
}

• 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? – Legato Feb 3 '15 at 16:20
• @Legato 1 liners are hard to read most of the time, since it's compacting everything. – Marc-Andre Feb 3 '15 at 16:29
• 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? – Legato Feb 3 '15 at 16:31
• By Java code convention you should not use one liners. See 7.4 in oracle.com/technetwork/java/javase/documentation/… – barq Feb 3 '15 at 16:48
• Regarding the library method: more importantly, it can be JITed to POPCNT, a single x86 instruction. – wchargin Feb 3 '15 at 21:22