[CC150] Chapter 5 Bits Manipulation

5.1 You are given two 32-bit number, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
EXAMPLE
Input:  N = 10000000000, M = 10011, i = 2, j = 6
Output: N = 10001001100

 Using bitset is trivial...

Better solution should be use a mask. According to the solution, the problem can be divided into three steps: 1) clear the bits j through i in N; 2) Shift M so that it lines up with N; 3) Merge M and N.

 5.2 Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR".

 Note that in the following code, I did not print "ERROR" for more than 32 bits. 
5.3 Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

 TBF.

 5.4 Explain what the following code does: ((n & (n - 1)) == 0).

 Suppose n = abcde1000 in binary. n - 1 is then abcde0111. n & (n - 1) is abcde0000. Hence, in order to make sure that n & (n -1) == 0, abcde have to be all zero. In other words, n has to be a power of 2 or 0.

 5.5 Write a function to determine the number of bits required to convert integer A to integer B.
EXAMPLE
Input: 31 = 11111, 14 = 01110
Output: 2

 It is equivalent to count the number of 1s in A ^ B. One way is to use bit shift; another tricky approach is to continuously flip the least significant bit ( c = c & (c - 1) ).
5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible.

 TBF.

 5.7 An array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bits of A[i]," which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

 TBF.

 5.8 A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows). The height of the screen, of course, can be derived from the length of the array and the width. Implement a function which draws a horizontal line from (x1, y) to (x2, y).

TBF.

Comments

Post a Comment

Popular posts from this blog

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.  Try to solve it in linear time/space.  Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. In order to solve this in linear time, we cannot use general sorting algorithm. Here we use bucket sort. First, we scan the array to find the min and the max values.   We can then create n - 1 buckets with equal size. Suppose we have n elements in total, then we have n - 2 elements except the min and the max. Scan the array again to put the n - 2 elements into these buckets. We should have at least one empty bucket. For each bucket, we record the min and the max for all the elements within that bucket.  Finally, we scan all the buckets, and maintain the maximum gap. Note that the maximum gap between the successive elements in the sorted array can only be the gap between
Read more

[ITint5] Maximum Subarray for a Circular Array

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this.
Read more

[CC150] Chapter 8 Object-Oriented Design

8.1 Design the data structure for a generic deck of cards. Explain how you would subclass the data structures to implement blackjack. Following codes implement blackjack. Note that syntax highlighter automatically changes some upper case letters to lower case.   8.2 Imagine you have a call center with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can't handle the call, he or she must escalate the call to a manager. If the manager is not free or not able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCall() which assigns a call to the first available employee. 8.3 Design a musical jukebox using object-oriented principles. 8.4 Design a parking lot using object-oriented principles. 8.5 Design the data structures for an online book reader system. 8.6 Implement a ji
Read more