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

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^x 你可以用一个 2^x+1...至于实际算法，因为您不需要关心 A 成员的顺序，您应该将它们全部放入 bag/multiset 结构中，并且构建 B 时从那里开始。

Answer 2

# 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 3

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

这是我在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;
    
}

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

Bit Manipulation, find another shortest array whose binarian is same as the given array's binarian

python

algorithm

bit