Part One

The goal here is to implement the method f in this file so that it returns the number of ones in the binary representation of its input integer, which you can assume to be positive. For example f(6) should output 2 and f(32) should output 1. Implement f as a recursive method using the idea that the number of ones in binary representation of x can be computed in terms of the number of ones in binary representation of the integer x/2.

Part Two

Here, provide the implementation for the methods union and intersect here . Both methods take as input two lists of Integer objects, and we can assume that the integers occur in increasing order (with no duplicates). The method union should return a list containing the union of the integers in the two input lists. The method intersect should return a list containing the intersection of the integers in the two lists.

The output lists need not be sorted, but they should not contain duplicates. Use only the basic list and iterator methods to implement these two functions. Try to make both methods as efficient as you can in the big-O sense. That is, if we let N denote the sum of the sizes of the two lists, an implementation with O(N) running time guarantee is preferable to an implementation with only an O(N^2) running time guarantee.

Please submit the two parts in separate files.