logo标签列表

整数的二进制表示中零的个数

calgorithm
9
给定一个32位整数N，设计一种算法来查找N的二进制表示中零的数量。
我能想到的最简单的算法是检查二进制表示中的零，在C语言中可能是这样的：

可能重复：
在32位整数中计算设置位数的最佳算法是什么？

我能想到的最简单的算法是检查N的二进制表示中的零。在C语言中可以这样实现：

int num_of_zero(int num)
 {
   if(0 == num) return 1; /*For the input 0 it should output 1 */
   int Count = 0;
   while(num>0){
     if(0 == (num&1)) Count++;
    num >>= 1;
}
return Count;
}

我在想是否有一些算法能够在常数时间内计算。
对于输入0，它应该返回1而不是32。
对于5，输出应该是1。因为二进制表示为101。
对于7，输出应该为0。
准确地说，我正在寻找更好的算法来计算32位整数二进制解释中非前导零的数量。希望问题现在清楚了。 编辑: 正如Alex Martelli、delroth指出的，我正在修改我的代码以使其更易读，并使用迭代。
重复。请参见https://dev59.com/23VD5IYBdhLWcg3wDG_m - ChrisInEdmonton
1
我不太喜欢在 OP 有机会回答问题之前批改作业。在 SO 上，有很多自学的人的先例。而且，如果这确实是作业，并且他们使用了从网络上完全复制的解决方案，他们几乎肯定会因为抄袭而失败（如果他们的教育者有一点智慧的话）。 - paxdiablo
@nthrgeek，如果这是作业，请标记它。 - paxdiablo
哦，我不认为这是技术上的重复 - 那个参考文献要求一位，这是微妙不同的 - 你不能使用当值为零时提前停止的技巧，因为正如@AlexM在他出色的答案中指出的那样，你会错过前导零。 - paxdiablo
1
@paxdiablo：不，这不是一个家庭作业问题，我正在寻找一些更好的算法，因为这个算法的时间复杂度是O(n)。 - whacko__Cracko
显示剩余6条评论
7个回答
6
简单的方法是迭代数值的二进制表示中的每个位，测试每个位的值，并计算其中有多少个零。对于这种情况，使用循环比递归更清晰。
当然，还有许多更优化的方法可以实现这一点。您可以在回答这个问题 "Best algorithm to count the number of set bits in a 32-bit integer" 中找到一些更好的方法。(显而易见，零位的数量是总位数减去设置位的数量)。
这个更简单，我知道它，有更好的算法吗？就像我们用于设置位的那个一样？ - whacko__Cracko
你可以使用任何这些算法，因为设置位和未设置位的数量之和是位数的总数。如果你想知道非前导零的数量，你可以使用数字的以2为底的对数来确定最高设置位的索引；也有快速查找此值的算法。 - James McNellis
2
Bit Twiddling Hacks 网站是 Suppressingfire 在他的回答中提到的，该网站有多种方法可以找到以 2 为底的对数：http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious - James McNellis
谢谢你告诉我关于以2为底数的对数问题，加1赞一个 :)。但是请问你能否帮我理解这如何有助于降低这个问题的复杂性？ - whacko__Cracko
1
一个无符号整数N中非前导零的数量与[((2^(lg2(N))-1) & (~N)]中设置的位数相同。 - Suppressingfire
6
4

快速而简单的方法--在重复的问题中有更多奇特的实现，但我过去使用过类似于这样的方法，并没有太大的负面影响。

我们在这里使用一张nibbles表格来减少循环次数--如果你要进行大量这样的计算，建立一个更大的数组可能更有效率，比如在字节级别上，可以将循环次数减半。

/* How many bits are set in every possible nibble. */
static size_t BIT_TABLE[] = {
    0, 1, 1, 2,     /* 0, 1, 2, 3 */
    1, 2, 2, 3,     /* 4, 5, 6, 7 */
    1, 2, 2, 3,     /* 8, 9, A, B */
    2, 3, 3, 4      /* C, D, E, F */
};

size_t num_of_bits(int num) {
    /* Little reworking could probably shrink the stack space in use here. */
    size_t ret = 0, i;
    register int work = num;

    /* Iterate every nibble, rotating the integer in place. */
    for(i = 0; i < (sizeof(num) * 2); i++) {
        /* Pointer math to get a member of the static array. */
        ret += *(BIT_TABLE + (work & 0xF));
        work >>= 4;
    }
    return ret;
}
2

递归肯定是过度设计了 - 而且，你的代码相当有缺陷（它不会计算任何num的前导零！！！）。 一个简单的迭代，例如：

int num_of_zero(int num) {
  unsigned int unum = (unsigned int)num;
  int count;
  int i;

  for(i = 0; i < 32; ++i) {
    if(!(unum & 1)) ++count;
    unum >>= 1;
  }
  return count;
}

以下是正确且更快的方法（可以编写更简洁的代码，但我认为这是最清晰的表达方式）。

如果您需要多次执行此计算，请考虑预先计算一个256个“零计数”的数组（每个值都作为8位数字给出其索引0到255的计数）。然后，您只需循环4次（每次遮盖和移位8位），并且可以轻松展开循环——如果您的编译器无法自动完成；-）。

谢谢，我不想计算任何前导零。 - whacko__Cracko
有趣的是，你在问题的编辑中完全和彻底地改变了你的规格 - 不是在一开始就表达出正确的规格更好吗？此外，如果你现在说你不想计算任何前导零，那么在你最近编辑答案时声称结果为1，这怎么可能呢？你想要计算的那个零是“前导”的。看来你将不得不特殊处理那个奇怪的异常值 - 唯一一个你确实想要计算前导0的情况！-) 除此之外，使用while(unum)作为循环而不是for等会很好用。 - Alex Martelli
抱歉，但我当时尝试编辑问题，但每次都出现503错误！ - whacko__Cracko
是的，我也遇到了很多500错误。不过，无论如何，最终结果是相似的，除了递归之外，还清除了其他荒谬之处，比如那个static。 - Alex Martelli
很奇怪，我的评论消失了？！但是肯定要谢谢 :) - whacko__Cracko
正如您和其他人所指出的，我已经修改了我的代码，希望现在没有问题 :-) - whacko__Cracko
2
我猜这是一个作业问题。没问题！以下是最快的解决方案（启动成本很高）：
创建一个长度为2^32的byte数组。预先计算每个可能的int值的二进制表示中零的数量，以填充该数组。从那时起，您将拥有一个可以给出每个值的零数的数组。
是的，这个解决方案很愚蠢——它需要大量的工作才能获得少量的收益——但结合另一个想法：
如果只预先计算8位长的值会发生什么？你能写出代码来，虽然不是那么快，但仍然能返回int中0位的数量吗？
如果只预先计算4位长的值会发生什么？2位长的呢？1位长的呢？
希望这能给您提供更好算法的灵感...
哇塞，一个 40 亿字节的数组。我差点就要给你点个踩，直到我看到你的意图 :-) - paxdiablo
当这个问题首次提出时，我写了这个评论。然后Stackoverflow崩溃了，没来得及提交。等我回来时，其他人已经回答了这个问题。我希望我的答案仍然能够显示出来。是的，paxdiablo - 原始答案确实很愚蠢。但我希望它能给出一些更好的想法。 - Chip Uni
1
也许SO崩溃是因为它尝试计算4GB的查找表时耗尽了内存... :-) 无论如何，我认为这是一个好答案（+1）。 - James McNellis
1

这并不是你主要问题的答案，但你应该像这样重写你的递归函数：

int num_of_zero(int num)
{
    int left_part_zeros;

    if (num == 0)
        return 0;

    left_part_zeros = num_of_zero(num >> 1);
    if ((num & 1) == 0)
        return left_part_zeros + 1;
    else
        return left_part_zeros;
}

你的实现有很多问题，而且完全无法读懂。

1

我发现最简单的方法是基于一个计算二进制中1的函数，然后从32中减去该函数的结果（假设您确信int的大小为32位）。

int numberOfOnes (int num) {
    int count = 0;
    unsigned int u = (unsigned int)num;
    while (u != 0) {
        if ((u&1) == 1)
            count++;
        u >>= 1;
    }
    return count;
}
int numberOfZeros (int num) {
    return 32 - numberOfOnes (num);
}

这实际上给出了两种变体（一和零）- 有更快的方法来完成，但除非你知道存在性能问题，否则我不会考虑它们。 我倾向于首先为可读性编码。

您可能还想至少测试一下表查找可能更快的可能性（优化的主要原则是测量，而不是猜测！

其中一个可能性是用每次操作四位二进制数的方式替换numberOfOnes函数：

int numberOfOnes (int num) {
    static const count[] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
    };
    int retval = 0;
    unsigned int u = (unsigned int)num;
    while (u != 0) {
        retval += count[u & 0x0f]
        u >>= 4;
    }
    return retval;
}
如果这就是我所寻找的，我最好使用 while(num) { count++;num &=(num - 1) } 来计算设置位的数量。 - whacko__Cracko
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接