6

我在一次采访中遇到了以下问题，我相信我给出了一个有效的实现，但我想知道是否有更好的更快的实现，或者只是我错过了一个技巧。

给定 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

现在组合这些集合并计算不同的条目。这就是答案。有没有办法在不枚举值的情况下做到这一点？

编辑：对不起这个问题的错误。现在修好了。

4

4 回答 4

7

编辑：更新要求：给定 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;
}
于 2012-05-01T17:29:20.237 回答
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)。结果，使用超级我可以计算出所有这些集合的大小。

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

于 2012-05-01T17:55:02.383 回答
0

技巧1：

总的答案是每个单独的 30 位数字的并集。这转换为按位联合运算符 OR。这意味着我们可以D = A | B | C 使用您的 4 位示例，我们到达D = 1111 现在我们只需要使用 1 个数字

技巧2：

一点点数学告诉我们，每1增加一倍我们可能的数字集。这意味着您需要做的就是将 2 提高到 1 的数量的幂。循环数1，每次向下移动

bits = 0
D = 0b1111 #our number from trick 1
for i in range(4): #here 4 is the number of bits
    if D & 1:
        bits += 1
    D >>= 1 #drop off the smallest number
print 2 ** bits

在这种情况下，它将打印 16

于 2012-05-01T17:17:30.537 回答
0

在 C# 中计算零的数量。许多零，你可以用给定的数字屏蔽的多种方式。因此，零的数量将使需要考虑的数字数量的变化=>这将是 2^（零计数）。

然后累积每三个数字的总匹配数。这里有些数字可能会翻倍。所以减去那个数字。添加为前一个数字减去的常用数字（按照三个重叠圆圈的范图）。

public static int count(int d)
    {
        int bits = 0;
        for(int i = 0; i < 30; i++)
        {
            if(((d>>i)&1)==0) bits++;
            //if ((d & 1) == 0) bits++;
            //d >>= 1; //shift right
        }
        return (int)Math.Pow(2, bits);
    }
    public static int BitWiseConfirm(int A, int B, int C)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int total = 0;
        total += count(A);
        //Console.WriteLine("total"+total);
        total += count(B);
        //Console.WriteLine("total"+total);
        total += count(C);
        //Console.WriteLine("total"+total);
        //remove duplicates
        total -= count(A | B);
        //Console.WriteLine("total"+total);
        total -= count(B | C);
        //Console.WriteLine("total"+total);
        total -= count(C | A);
        //Console.WriteLine("total"+total);
        total += count(A | B | C);
        //Console.WriteLine("total"+total);
        return total;
    }
于 2022-01-29T10:08:18.110 回答