计数位掩码,枚举0

Question

我在接受采访时遇到了以下问题,我相信我提供了一个有效的实施方案,但我想知道是否有更好的实施更快,或者只是我错过了一个技巧.

给定3个无符号30位整数,返回30位整数的数量,与任何原始数字相比,将相同的位置位设置为1.即我们枚举所有的0

让我举个例子,但为了清晰起见,我们使用4bit.

鉴于:

A = 1001
B = 0011
C = 0110

它应该返回8,因为集合中有8个4位的整数.该集是:

0011
0110
0111
1001
1011
1101
1110
1111

现在我如何解决这个问题就是取每个数字并枚举一组可能性,然后计算所有不同的值.我如何枚举该集合是从数字开始,添加一个,然后与它自己或它直到我到达掩码.数字本身在集合中,掩码(全部设置为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

B:

0011
0111
1011
1111

C:

0110
0111
1110
1111

现在组合这些集合并计算不同的条目.这就是答案.有没有办法在不枚举值的情况下执行此操作？

编辑:对不起这个问题的错误.现在修复了.

Answer 1

编辑:更新要求:给定3个无符号30位整数,返回30位整数的数量,与任何原始数字相比,将相同位置位设置为1.即我们枚举所有0

好吧,这有点难度.计算一个数字很容易,因为在这种情况下,可能的整数数量仅取决于零位数,如下所示:

// Count bits not set
const size_t NUMBITS=30;
size_t c;
size_t v = num;
for (c=NUMBITS; v; v >>= 1) 
  c -= v & 1;

return c; 

天真地你可以尝试将它扩展到三个整数,为每个整数和总结结果,但这是错误的,因为可能性需要是唯一的,例如给定

A = 1001
B = 0011
C = 0110

你会计算三次1111而不是一次.您应该减去任意两个数字之间共享的组合数,但不能减去任何两次组合. 这只是Winston Ewert答案的C++翻译!

size_t zeroperms(size_t v)
{
    // Count number of 0 bits
    size_t c = 1;
    for (c=NUMBITS; v; v >>= 1)
        c -= v & 1;
    // Return number of permutations possible with those bits
    return 1 << c;
}

size_t enumerate(size_t a, size_t b, size_t c)
{
    size_t total = zeroperms(a) + zeroperms(b) + zeroperms(c);
    total -= zeroperms(a | b); // counted twice, remove one
    total -= zeroperms(b | c); // counted twice, remove one
    total -= zeroperms(a | c); // counted twice, remove one
    total += zeroperms(a | b | c); // counted three times, removed three times, add one
    return total;
}

Answer 2

N = 4

def supers(number):
    zeros = sum(1 for bit in xrange(N) if (number >> bit) & 1 == 0)
    return 2**zeros


def solve(a,b,c):
    total = supers(a) + supers(b) + supers(c)
    total -= supers(a | b) # counted twice, remove one
    total -= supers(b | c) # counted twice, remove one
    total -= supers(a | c) # counted twice, remove one
    total += supers(a | b | c) # counted three times, removed three times, add one

    return total


print solve(0b1001,0b0011,0b0110)

解释

让S(n)是 由数字 产生的集合n。

supers(n)返回|S(n)|数字 n 的集合的大小。supers不是一个好名字，但我很难想出一个更好的名字

诀窍是要意识到这一点S(a) ^ S(b) = S(a | b)。因此，使用 supers 我可以计算出所有这些集合的大小。

要弄清楚其余部分，请绘制集合的维恩图。