Friday, March 21, 2014

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

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/.
Problem
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 
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       2   
Bits 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