Looping назад через высокие биты порядка в ряде

Question

У меня есть функция, которая принимает целое число и возвращает набор, который состоит из степеней 2, сумма которых равно значение входного сигнала:

def bin_set(n): 
    b = set() 
    while n: 
     hbit = 1 << n.bit_length()-1 
     b.add(hbit) 
     n -= hbit 
    return b 

Так рассчитать старший бит числа и добавьте его в набор, но какое значение n следует отправить на следующую итерацию цикла? Я использовал n = n-hbit из-за состояния while, и это как-то работает, но я уверен, что это неправильный подход.

Есть ли другой способ сделать это, возможно, с другим циклом и без логарифмов/бит twiddling/bit_length() или это единственный подход?

Answer 1

Подход работает очень хорошо; вы удаляете обнаруженный бит с n с вычитанием, пока не удалите все биты. В результате результат n.bit_length() также уменьшается.

Вместо вычитания, вы можете использовать XOR (^ оператор), чтобы очистить старший бит:

def bin_set(n): 
    b = set() 
    while n: 
     hbit = 1 << n.bit_length() - 1 
     b.add(hbit) 
     n ^= hbit 
    return b 

Другой подход был бы для сдвига вправо старший бит, а не изменяя n:

def bin_set(n): 
    b = set() 
    hbit = 1 << n.bit_length() - 1 
    while hbit: 
     if n & hbit: # the high bit is set 
      b.add(hbit) 
     hbit >>= 1 
    return b 

но это на самом деле больше тестов!

Ваша версия только петли столько раз, сколько битов установлено в n, но вычисляет количество бит каждой итерации, в то время как вышеперечисленные версии петель n.bit_length() раз. int.bit_length() занимает среднее время O (N) для вычисления длины бита, поэтому ваш принимает время O (KN) для создания набора значений K из N бит, сдвигая высокий бит на время O (N).

Это делает мою версию лучше асимптотически, но поскольку метод int.bit_length() выполняет работу на C и уменьшает цикл до одной итерации цикла на 4 бита, это не так плохо, как кажется. Вам нужно humongous номеров, прежде чем вы начнете видеть мою победу.

Answer 2

Вы можете использовать что-то, называемое set comprehension, что является очень кратким способом их создания.

def bin_set(n): 
    return {1 << p for p in xrange(n.bit_length()-1, -1, -1) if n & 1 << p} 

print bin_set(0) # --> set([])   
print bin_set(10) # --> set([8, 2])  
print bin_set(12) # --> set([8, 4])  
print bin_set(15) # --> set([8, 1, 2, 4])