This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/set-all-bits-of-a-number-in-a-range-equal-to-another-number/.
ProblemYou 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
Consider the integer N, where we want to fit in M between bits i and j of N.
Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100
i=2 j = 6 1000 | ----- | 00 6 2Bits count start from left to right, starting with index 0.
Solution
Method 1
- Set the bits being modified to 0 via the mask
- Set the bits being modified to the values of m via the
| (m << i)
int fitInteger(int n,int n, int i, int j) { /* bitwise not of (1s from j to the end) - (1s from i to the end) */ unsigned int mask = ~ ( ((1 << (j-i)) - 1) - ((1 << i) - 1) ); return (n & mask ) | (m << i); }
Writing in simpler terms:
Logic is basically to create a mask that consists of 1's in all positions except from position i to position j.
- 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.
- 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.
- OR N and M.
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); }
Dry running the program:
N = 1010 1011 1101 1110 M = 1001 0110 i = 4, j = 11. i.e : should be doing: 1010|---- ----|1110 11 4 max = 1111 1111 1111 1111 left(j) = 1111 1000 0000 0000 right(i) = 0000 0000 0000 0111 mask = 1111 1000 0000 0111 //Computing left = max - ((1 << (j+1)) - 1) ------------------------- left ----------------------------- (1<<(j+1)) 0001 0000 0000 0000 //shift 1 - 12 times as j+1 is 12 1 0000 0000 0000 0001 - // minus ------------------- (temp) 0000 1111 1111 1111 (max) 1111 1111 1111 1111 (temp) 0000 1111 1111 1111 - // minus ------------------- (left) 1111 0000 0000 0000 ------------------------------------------------------------ //Computing right=((1 << i) - 1); ----------- right ----------- ----------------------------- (1<<i) 0000 0000 0001 0000 //left rotate 1 4 times (as i=4) 1 0000 0000 0000 0001 - // minus ------------------- (right) 0000 0000 0000 1111 ------------------------------------------------------------ //Compute mask = left | right (left) 1111 0000 0000 0000 (right) 0000 0000 0000 1111 | ------------------- (mask) 1111 0000 0000 1111 ------------------------------------------------------------ //Compute result = (n & mask) | (m << i) ----------------------------- ---------------------------- (n) 1010 1011 1101 1110 (mask) 1111 0000 0000 1111 & //and operator ------------------- (tmp1) 1010 0000 0000 1110 ------------------- (tmp1) 1010 0000 0000 1110 (m<<i) 0000 1001 0110 0000 | //or operator (result) 1010 1001 0110 1110 -------------------------------------------------------------
Reference - stackoverflow
0 comments:
Post a Comment