Учитывая два 32-разрядных числа, N и M, и две разрядные позиции, i и j. напишите метод, чтобы установить все биты между i и j в N равными M

Вам даны два 32-разрядных числа, N и M, и две разрядные позиции, i и j. напишите метод, чтобы установить все биты между i и j в N равными M (например, M становится подстрокой N, расположенной в i и начинающейся в j). Пример: вход: N = 10000000000, M = 10101, i = 2, j = 6 выход: N = 10001010100

Эта проблема возникает из-за взлома кодирующего интервью. Я смог решить ее с помощью следующего алгоритма O(j - i): 

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

Автор дал этот алгоритм O(1) в качестве решения:

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)
Я заметил, что для некоторых тестовых случаев алгоритм автора, похоже, выдает неправильный ответ. Например, для N = 488, M = 5, i = 2, j = 6 он выводит 468. Когда выход должен быть 404, как это делает мой алгоритм O (j-i).

Вопрос: Есть ли способ получить алгоритм постоянного времени, который работает для всех случаев?

4 4
python algorithm bit-manipulation bitwise-operators

4 ответа:

Я думаю, что автор алгоритма предполагает, что граница 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 и т. д.) и то и другое должно всегда давать один и тот же результат.

7

Я думаю, что в предлагаемом решении есть одна ошибка.

Это должно быть: 

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)
4

  1. Создайте маску m, которая установила биты для всех битов между <i,j>

    Вы можете использовать арифметический сдвиг битов влево для создания степеней 2, используя то, что степени 2 минус один являются числами со всеми установленными битами до экспоненты-1 поэтому установите все биты <0,j> , а затем очистите биты до i-1

  2. Копировать биты из M в N

    Поэтому используйте m для очистки битов в N, а затем скопируйте вместо них биты M. Не забывайте перекладывать слева M от i, чтобы соответствовать вашему случаю...

В C++ (извините, не используйте 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 числа, если вы не чувствуете себя комфортно с битовыми сдвигами...

2

Эта версия, кажется, тоже хорошо работает, при условии i <= j 

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