建设一个合乎逻辑的前pression将在一个字节计数位 [英] Construction an logical expression which will count bits in a byte

问题描述

在面试新的候选人，我们通常会问他们写一张C code在一个给定的字节变量值为1来计算的位数（例如字节3有两个1位）。我知道所有的答案常见，如右移八次，或索引的256 $ P $常数表pcomputed结果。

When interviewing new candidates, we usually ask them to write a piece of C code to count the number of bits with value 1 in a given byte variable (e.g. the byte 3 has two 1-bits). I know all the common answers, such as right shifting eight times, or indexing constant table of 256 precomputed results.

不过，有没有使用pcomputed表中的$ P $一个更聪明的方式？什么是字节操作（AND，OR，XOR，+， - ，二元否定，左，右移动）的最短组合？它计算的1位的数量

But, is there a smarter way without using the precomputed table? What is the shortest combination of byte operations (AND, OR, XOR, +, -, binary negation, left and right shift) which computes the number of 1-bits?

推荐答案

有至少两个快溶液，具有不同的性能特点：

There are at least two faster solutions, with different performance characteristics:

1. 减之一，并与新老值。重复，直到为零。计数迭代次数。复杂度：O（B），其中B是一个位的数量

1. Subtract one and AND the new and old values. Repeat until zero. Count the number of iterations. Complexity: O(B), where B is the number of one-bits.

int bits(unsigned n)
{
    for (int i = 0; n; ++i)
    {
        n &= n - 1;
    }
    return i;
}

添加位双然后四人一组，那么八组，直到你到达字的大小。有一个窍门，可以让你添加的所有组在每个级别在一个单一的通行证。复杂度：O（日志（N）），其中N是位总数

Add pairs of bits then groups of four, then groups of eight, till you reach the word size. There's a trick that lets you add all groups at each level in a single pass. Complexity: O(log(N)), where N is the total number of bits.

int bits(uint32 n)
{
    n = (n & 0x55555555) + ((n >>  1) & 0x55555555);
    n = (n & 0x33333333) + ((n >>  2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >>  4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >>  8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + (n >> 16);
    return n;
}

这版本是有点幼稚。如果你想想一下，就可以避免某些操作。

This version is a bit naive. If you think about it a bit, you can avoid some of the operations.

这篇关于建设一个合乎逻辑的前pression将在一个字节计数位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！