Number of ones in the binary representation

Let us state the relevant knowledge in the form of equivalences. 'If and only if' is abbreviated as iff.

1. The binary representation of  \( n \) has  \(0\) ones iff  \(n\) is  \(0\).
2. The binary representation of  \(n\) has  \(b\) ones iff  binary representation of  \(n & n-1\) has  \(b-1\) ones.
3. When the last binary digit is 1, the binary representation of  \(n\) has  \(b\) ones iff  binary representation of  \(n >>> 1\) has  \(b-1\) ones.
4. When the last binary digit is 0, the binary representation of  \(n\) has  \(b\) ones iff  binary representation of  \(n >>> 1\) has  \(b\) ones.

These can easily be verified and proved.  We can also state them directly as recursive methods in java. Important thing to notice is that we do not need all the properties. First two properties give us recur method. Last two together with the boundary condition that is the very first property give us recurWithShift method . 

public class numOnesInBinary {

public static int recur(int n){
if (n == 0) return 0;                 // From 1
return 1 + recur(n & n-1);// From 2
}

public static int recurWithShift(int n){
if (n == 0)       return 0;
if ((n & 1) == 1) return 1 + recur(n >>> 1); // From 3
return     recur(n >>> 1); // From 4
}

public static void main(String[] args) {
System.out.println(recur(7895));
System.out.println(recurWithShift(7895));

}
}