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

}
}

Separate implications from equivalences before coding

I learned my math in Telugu up to 10th grade. I vividly recall the teacher admonishing us whenever we mistake implication as equivalence. He used to shout  " ViNiKa (Vilomamu Nijam Kadu)". That means 'Converse is not true'. His pet example was similarity of triangles does not imply congruence.

I suppose the art of funny conversation in a natural language like Telugu, English or Sanskrit consists of mistaking implication as equivalence. I recall an incident when an elderly gentleman blessed a young person 'Deerghaushman Bhava' ( May you live long!), the young person retorted "Papi Chirauh (Sinners live long.) Do you want me to become a sinner?". The elderly gentleman was shocked that his blessing could be interpreted that way.  I explained ViNiKa (Vilomamu Nijam Kadu)  and wished virtuous life for the young person and spoiled the fun.

Every computer program is a theory in the relevant domain of discourse. A counterexample to the theory is a test designed to show that the theory is not true. Sometimes it is easier to prove a theory correct than coming up with a counterexample that demonstrates  the theory is not true. There are times when a counterexample is easy and futile attempts at proving wrong theories can be avoided. It is prudent that a software developer keeps both proving and testing in mind during development.

Let us consider a faulty java method to check whether two given strings are equal.

public static boolean iterCheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
    equal =  (s1.charAt(i) == s2.charAt(i));
}
    return equal;
}

The pair (cut, bat) is a counter example. The theory is false. What is wrong?
Equality of strings implies the equality of last character in the strings. Converse is not true. (ViNiKa).
Are there any equivalences in the domain of discourse of the problem? Yes.

1. Character comparison failure is equivalent to inequality of strings.
2. Success of every character comparison is equivalent to equality of strings.

We can modify the above program by incorporating the two equivalences and getting rid of the declaration of a boolean.

public static boolean elegantCheck(String s1, String s2) {
   for (int i=0; i < s1.length(); i++){
    if(!(s1.charAt(i) == s2.charAt(i))) return false; //From 1.
  }
   return true; // From 2.
}

Moral of the story: Recognize the implications and equivalences before coding.
School Math Sufficient for  Program Correctness Proving (SMSPCP)