Битовая манипуляция, найдите другой кратчайший массив, бинарник которого совпадает с бинарником данного массива

Question

Для массива A его binarian(A) определяется как 2 ^ A [0] + 2 ^ A [1] + .... 2 ^ A [n];Вопрос просит найти самый короткий массив B, чей binarian(B) такой же, как и у A.

Например, A=[1,0,2,0,0,2] ，, таким образом, если B=[3,2,0], это удовлетворяет требованиям, и результат равен 3.

Не могли бы вы, ребята, дать некоторые идеи, как решить эту проблему? Благодарю.

Answer 1

# find the binarian
binarian = sum(2**a for a in A)
# find the powers of two that are present in A
# We do this by making a list of which bits are True in the binarian.
#   we check each bit, using len(bin()) to as an easy log2
#   we only include powers of two that produce 1 when and'ed with the binarian
B = [pwr for pwr in range(len(bin(binarian)) - 2) if (2**pwr & binarian)]

Нет более эффективного способа построить число из степеней двух, чем просто перечислить, какие биты перевернуты. Это то, что это делает. Он просматривает биты от наименее значимого к наиболее значимому и выводит только, если бит перевернут.

Это создает восходящий список (например, [0, 2, 3]. Если вы хотите нисходящий список (например, [3, 2, 0])Вы можете заключить вызов range() в reversed().

Answer 2

Вот решение, в которое мы добавляем степень 2, делающую перенос переноса вручную. Он может обрабатывать тупо большие входные данные, такие как A=[1000000000, 1000000000, 1000000001].

def shortest_equivalent_binarian(A): 
   s = set() 
   for a in A: 
       while a in s: # carry propagation
           s.remove(a) 
           a += 1 
       s.add(a) 
   return sorted(s, reverse=True)
# reverse is not necessary for correctness, but gives the same B as in your example

Answer 3

Без прямого ответа на то, что звучит как вопрос о задании, я просто укажу, что в любой момент, когда у вас есть пара 2 ^x , вы можете заменить ее на одну 2 ^{x + 1} ... Что касается фактического алгоритма, так как вам не нужно заботиться о порядке членов A, вы должны поместить их всех в структуру bag / multiset и перейти оттуда к построению B.