我在一次采访中遇到了以下问题,我相信我给出了一个有效的实现,但我想知道是否有更好的更快的实现,或者只是我错过了一个技巧。
给定 3 个无符号 30 位整数,返回 30 位整数的个数,当与任何原始数字比较时,具有相同的位置位设置为 1。也就是说,我们枚举所有的 0
让我举个例子,但为了清楚起见,让我们使用 4bit。
鉴于:
A = 1001
B = 0011
C = 0110
它应该返回 8,因为集合中有 8 个 4 位整数。集合是:
0011
0110
0111
1001
1011
1101
1110
1111
现在我的计算方法是获取每个数字并枚举一组可能性,然后计算所有不同的值。我枚举集合的方式是从数字开始,向其添加一个,然后将其与自身 OR 直到我到达掩码。数字本身在集合中,掩码(全部设置为 1)也在集合中。因此,例如枚举 1001 的集合:
1001 = the start
1011 = (1001 + 1) | 1001
1101 = (1011 + 1) | 1001
1111 = (1101 + 1) | 1001 (this is the last value as we have reached our mask)
所以对每个数字都这样做,然后计算唯一性。
这就是python代码中的内容(但是只要您可以进行按位运算,语言并不重要,因此为什么这个问题也被标记为c / c ++):
MASK = 0x3FFFFFFF
def count_anded_bitmasks( A, B, C ):
andSets = set(
enumerate_all_subsets(A) +
enumerate_all_subsets(B) +
enumerate_all_subsets(C)
)
return len(andSets)
def enumerate_all_subsets( d ):
andSet = []
n = d
while n != MASK:
andSet.append(n)
n = (n + 1) | d
andSet.append(n)
return andSet
现在这有效并给出了正确的答案,但我想知道我是否错过了一个技巧。由于问题是只询问计数而不枚举所有值,因此也许有一种更快的方法。要么先组合数字,要么在不枚举的情况下进行计数。我有一种感觉。由于包含大量零的数字,枚举呈指数增长,并且可能需要相当长的时间。
如果您有 AB 和 C,则将位设置为 1 的数字集的计数,其中 A、B 或 C 的相应位设置为 1。
有些人不理解这个问题(没有帮助我没有首先正确地问它)。让我们使用上面给定的 AB 和 C 值:
A:
1001
1011
1101
1111
乙:
0011
0111
1011
1111
C:
0110
0111
1110
1111
现在组合这些集合并计算不同的条目。这就是答案。有没有办法在不枚举值的情况下做到这一点?
编辑:对不起这个问题的错误。现在修好了。