Bit Manipulation,找到另一个最短数组,其二进位与给定数组的二进位相同

问题描述 投票:0回答:2

给定数组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。

你们能提供一些解决此问题的想法吗?谢谢。

python algorithm bit
2个回答
0
投票
# 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()中。]]


0
投票

[没有完全回答听起来像是分配问题的问题,我只是指出,只要您有一对2 x

© www.soinside.com 2019 - 2024. All rights reserved.