Set all bits of a number in a range equal to another number

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

My initial thoughts:

  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.

My initial codes:

	public static void setBits(int N, int M, int i, int j) {
		int mask = 1;
		for (int digit = i; digit <= j; ++digit)
			mask |= (mask << digit);
		N &= ~mask;
		M &= mask;
		N = N | M;
	}

Comments after running:
It does not work…

Solution:

	public static int updateBits(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);
	}

The idea is the same as mine but my implementation is wrong…

Advertisements

1 Comment (+add yours?)

  1. Som
    Sep 28, 2013 @ 02:07:07

    Correct Answer :
    public static int updateBits(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); // here should be j+1 not j.

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: