Sum of bits set

Q: Given a positive integer N calculate the sum of bits set for all the numbers from 0 to N.

I will be using divide and conquer for this. 

Fact: The sum of all set bits from 0 to (2 ^ n) - 1 is (2 ^ n-1) * n
This can be proved by induction or construction.

Approach:

1) Get the MSB location of the integer N, i.e. the left most bit which is set as 1, lets say it is X

2) Get the sum of all the bits till (2 ^ X) - 1 using the fact given above, lets say it is Sum

3) Now, add 1 for number (2 ^ X) to Sum

4) We are now left to calculate from (2 ^ X) + 1 to N. All these will have Xth bit set.
5) So add N - (2 ^ X) to Sum
6) Now we can solve for a smaller sub-problem using recursion. The numbers left are (2 ^ X) + 1 ..... N, with the Xth bit now turned off since we have already considered the Xth bit in step 5. This is equivalent to finding the sum of bits till N XOR (2 ^ X)

Code:
To get the MSB location we can again use divide and conquer to reduce the no. of steps.
http://graphics.stanford.edu/~seander/bithacks.html

Ideas taken from:
http://tech-queries.blogspot.in/2010/12/number-of-set-bits-till-n.html
http://code.rishibaldawa.com/count-all-set-bits-from-0-till-n-for-each-number

Duplicate & missing number

Q: In an unsorted array of first N natural numbers which has a duplicate number and a missing number, find the duplicate and missing numbers.

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Sum of N^2 numbers = n(n+1)(2n+1)/6

3. Since there are 2 unknowns we can create 2 equations using the above formulae to solve them

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Multiplication of N numbers / n! = Duplicate/Missing

3. Again we can solve for the 2 unknowns using the above formulae

Both the above approach assumes that N^2 or N! can be held in an int/double etc without overflow. In Java we can make use of BigInteger but there is another approach to solve the problem using bit operators.

Soln approach:

Let Ai be the ith element of the array, 0 <= i < n

Let Bi be i+1

1. Find Duplicate XOR Missing = X

    - XOR all Ai and Bi

2. Find which rightmost bit is 1 in X = Y

    - X & ~(X - 1)

3. Partition A and B such that A1 and B1 has Y set and A2 and B2 does not have Y set

    - Iterate and use & operator over Y and elements of A and B

4. XOR elements of A1 and B1 = VALUE1

5. XOR elements of A2 and B2 = VALUE2

6. If A1.length > B1.length then VALUE1 = Duplicate and VALUE2 = Missing

    else VALUE2 = Duplicate and VALUE1 = Missing

Online Image Manipulators

Today, I was just googling for the online image manipulators and found this blog entry worth keeping track of. Thanks for the info. Just to copy the most relevant information from that page:

A list of free online image editors:

* Snipshot
* Picnik
* FotoFlexer
* Pixer.us
* Pixlr
* Phixr
* WebPicTool
* Splashup
* Resizr
* Photoshop Express
* Imageeditor.net

JNDI and OC4J

Got stuck into something and considered it interesting to keep a note of. If you are a J2EE developer and using Oracle Application server (OC4J) then the following information may be useful.

In OC4J if you have user created threads (not implicit threads of Servlet etc) and you want to do a JNDI lookup in that thread, then an OC4J start-up option needs to be set, otherwise the lookup would fail. The option is "-userThreads" and can be set using EM console (OC4J -> Administration -> Server Properties -> Start-parameters: OC4J Options).

Here is the detail of all such available OC4J options.

IoC and DI

Good read on IoC and DI

http://martinfowler.com/bliki/InversionOfControl.html
http://martinfowler.com/articles/injection.html

Something that cleared my thought process (an excerpt from one of the articles)
Inversion of Control is a key part of what makes a framework different to a library.

Autoboxing and Equality

Tiger(JDK 5) has introduced a lot of features and in turn lots more to dig into. Here I want to explain the issues that arise due to equality comparisons and Autoboxing/Auto-unboxing.

Since, equality operator (==) can be used with reference variables and primitive types, the first question is what happens when we equate reference wrapper variable with its corresponding primitive type.

int i = 1;
Integer iObj = new Integer(i);
System.out.println(i==iObj);

Here, the iObj will be unboxed to a primitive type and the result of the expression would be similar to the comparison of int value with iObj.intValue().

If we equate two reference wrapper variables it is not the value comparisons but object comparison.

Also, JLS recommends that the same wrapper objects should be returned on autoboxing for lower values of the integer primitives. This accounts for some of the unusual behaviour of the equality expressions.

The program and the output below self-explains the issues

package autoboxing;

public class EqualityTest {

 public static void main(String[] args) {
  // any arbitrary value
  int i = 236459;
  Integer iObj = new Integer(i);
  
  /*
   *  if wrapper object is equated with primitive 
   *  types wrapper object would be converted to 
   *  primitive type and then compared
   */
  
  if(i == iObj) {
   System.out.println("Integers are equal: " + i);
  }
  
  for(int loop = -128; loop < Integer.MAX_VALUE; loop++) {
   Integer iObj1 = loop;
   Integer iObj2 = loop;
   
   /*
    * this is a reference equality check and not value 
    * comparison 
    */ 
   if(iObj1 == iObj2) {
    
   } else {
    System.out.println("Integers are not equal: " + loop);
    break;
   }
  }
  
  for(int loop = -128; loop < Integer.MAX_VALUE; loop++) {
   Integer iObj1 = new Integer(loop);
   Integer iObj2 = new Integer(loop);
   
   /*
    * this is a reference equality check and not value 
    * comparison 
    */ 
   if(iObj1 == iObj2) {
    
   } else {
    System.out.println("Integers are not equal: " + loop);
    break;
   }
  }
 }
}


Output:
Integers are equal: 236459
Integers are not equal: 128
Integers are not equal: -128

Calling non-public methods

A very small and simple hack to call non-public methods in Java.

Problem
~~~~~~~
A non-public method of a class has to be called from another class. Both the classes are in different packages.

package apipackage;
public class APIClass {
 void methodA() {
   System.out.println("methodA Called");
 }
}

package clientpackage;
public class ClientClass {
 void methodACaller() {
 ...
 ...
 ...
 }
}

Fill in the dotted lines to call methodA of APIClass.

Solution
~~~~~~~~

package clientpackage;
// import statements
public class ClientClass {
 void methodACaller() {
  apipackage.APIClass apiObject = new apipackage.APIClass();
  Method methodA = apipackage.APIClass.class.getDeclaredMethod("methodA", null);
  methodA.setAccessible(true); // this makes it possible to invoke methodA
  methodA.invoke(apiObject, null);
 }
}

One important thing to remember is to call "getDeclaredMethod" and not "getMethod" to obtain the Method object.

From Java docs:
"getMethod returns a Method object that reflects the specified public member method of the class"

/*
   This would not work
   Method methodA = apipackage.APIClass.class.getMethod("methodA", null);
*/