Saturday, January 21, 2012

Set subset of bits in X equivalent to ones in Y

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100


Solution:
  1. Create a mask with 1s but only 0s between positions i and j. AND the mask with N to clear the bits between i and j to 0s.
  2. Create another mask with 0s but only 1s between positions i and j. AND the mask with M to clear the bits outside i and j to 0s.
  3. OR N and M.
 Code:

int SetRangeBits(int n, int m, int i, int j) {
    int max = ~0; /* All 1's */

    // 1's through position j, then 0's
    int left = max - ((1 << j) - 1);

    // 1's after position i
    int right = ((1 << i) - 1);

    // 1's with 0s between i and j
    int mask = left | right;

    // Clear i through j, then put m in there
    return (n & mask) | (m << i);
}
 

Alternatively,
  1. Create a mask where the only zeroes are in bit positions i to j, which is ~(2j+1 - 2i)
  2. Result = (mask & X) | (Y << i)

Useful Links :
http://www.careercup.com/question?id=8863294

1 comment:

  1. how many bits does the mask occupies? I am not able to understand the solution.

    ReplyDelete