位操作，找到另一个最短的数组，其二进制数组与给定数组的二进制数组相同

Question

给定一个数组 A，其binarian(A)定义为 2^A[0] + 2^A[1] + ....2^A[n];问题要求查找binarian(B)与 A 相同的最短数组 B。

例如，A=[1,0,2,0,0,2]，因此如果B=[3,2,0]，则满足要求，输出为3。

你们能提供一些如何解决这个问题的想法吗？谢谢。

Answer 1

这是一个解决方案，我们添加 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 2

没有直接回答听起来像是作业的问题，我只想指出，任何时候你有一对 2^x你可以用一个 2^x+1代替它......至于实际的算法，因为你不需要关心A成员的顺序，你应该把它们全部放到一个袋子/多集结构中，然后在构建B时从那里开始。

Answer 3

这是我在PHP中的解决方案

function solution($a){
// write your code in PHP7.0
$binarian = 0;
foreach ($a as $val){
$binarian += pow(2, $val);
}
$b = [];
while($binarian > 0){
$el = intval(log($binarian, 2));
array_push($b, $el);
$binarian -= pow(2, $el);
}

return $b;

}

Answer 4

# 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)]

用 2 的幂构造一个数字，然后简单地列出哪些位被翻转，没有比这更有效的方法了。这就是它的作用。它扫描从最低重要到最重要的位，并且仅在位翻转时才输出。

这将生成一个升序列表(例如[0, 2, 3].如果您想要降序列表(例如[3, 2, 0]，您可以将range()调用包装在reversed()中。

Answer 5

这就是我在Javascript中解决这个问题的方式

function solution(A) {
let binarian = 0;
// only positive values
A = A.filter((x) => x > -1);
// get the total of the binarian
for (let i = 0; i < A.length; i++) {
binarian += Math.pow(2, A[i]);
}
// time to prepare your own binarian the shortest one!
let b = [];
while (binarian > 0) {
let element = parseInt(Math.log2(binarian), 10);
b.push(element);
binarian -= Math.pow(2, element);
}
return b.length;
}