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 to N equal to M

Question

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

This issue is related to Cracking the Coding interview. I was able to solve it using the following O (j - i) algorithm:

def set_bits(a, b, i, j):
    if not b: return a
    while i <= j:
        if b & 1 == 1:
            last_bit = (b & 1) << i
            a |= last_bit
        else:
            set_bit = ~(1 << i)
            a &= set_bit
        b >>= 1
        i += 1
    return a

The author gave this algorithm O (1) as a solution:

def update_bits(n, m, i, j):
    max = ~0 # All 1s

    # 1s through position j, then zeroes
    left = max - ((1 << j) - 1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

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

I noticed that for some test cases, the author's algorithm seems to output the wrong answer. For example, for N = 488, M = 5, i = 2, j = 6, it gives 468. When the output should be 404, like my algorithm is O (j - i).

: , ?

Answer 1

, , j ( ) ; , 2 6 6 ( Python ). , :

def update_bits(n, m, i, j):
    max = ~0 # All 1s

    # 1s through position j, then zeroes
    left = max - ((1 << (j+1)) - 1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

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

.

:

def update_bits(n, m, i, j):
    # 1s through position j, then zeroes
    left = (~0) << (j+1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

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

.

, , b = 0, , a, . a = '0b1011001111101111' b = '0b0' i j 6 8 , , '0b1011001000101111'. , :

def set_bits(a, b, i, j):
    while i <= j:
        if b & 1 == 1:
            last_bit = (b & 1) << i
            a |= last_bit
        else:
            set_bit = ~(1 << i)
            a &= set_bit
        b >>= 1
        i += 1
    return a

, 10'000'000 , :

for i in range(10000000):
    m = randint(0,65536)
    i = randint(0,15)
    j = randint(i,16)
    n = randint(0,2**(j-i))
    if set_bits(m,n,i,j) != update_bits(m,n,i,j):
        print((bin(m),bin(n),i,j,bin(set_bits(m,n,i,j)),bin(update_bits(m,n,i,j)))) #This line is never printed.

, , (, , ), , (i j , i < j ..), .

Answer 2

, .

:

def update_bits(n, m, i, j):
    max = ~0 # All 1s

    # 1s through position j + 1, then zeroes
    left = max - ((1 << (j + 1)) - 1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

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

, j i, j. 404.

, , m (j - i + 1) , return:

    return (n & mask) | ((m << i) & ~mask)

Answer 3

• m, <i,j>

  , 2, , 2 - -1 <0,j>, i-1

• m N

  m, N, m. m i ...

++ (, python) O(1) :

DWORD bitcopy(DWORD N,DWORD M,int i,int j)
    {
    DWORD m;
    // set bits <0..j>
    m =(2<<j)-1;
    // clears <0..i)
    if (i) m^=(2<<(i-1))-1;
    // clear space for copied bits
    N&=0xFFFFFFFF-m;
    // copy bits M->N
    N|=(M<<i)&m;
    return N;
    }

LUT i,j m... 32- , 32 64 , ...

Answer 4

This version also works well if i <= j

def set_bits(n, m, i, j):
    mask = (1 << (j + 1)) - (1 << i)
    return n & ~mask | (m << i) & mask