为什么此函数计算整数中设置的位数 [英] Why does this function count the number of set bits in an integer

问题描述

在一次采访中我被问到以下问题:

I was asked the following question in an interview:

int foofoo(unsigned int u) {
    unsigned int foo = u;
    do{
        u = u/2;
        foo -= u;
    }while(u > 0);
    return foo;
}

有人要求我告诉我此函数的作用，我发现它可以计算无符号int值中的置位位数，但我无法证明这一点，也许有人可以吗?

I was asked to tell what does this function do and I was able to find that it counts the number of set bits in an unsigned int value, but I was not able to prove that, maybe someone can?

推荐答案

想法

已知可以将无符号整数u表示为二次方的和:

The Idea

It is known that an unsigned integer u can be represented as a sum of powers of two:

u = A * 2ª + ... + N * 2ⁿ,

其中，0 <= a < ... < n是整数，而A, ..., N是零，或 那些.如果我们删除零积项，则项数将相等 到设置的位数(个).例如，1101 _b =2⁰+ 2²+2³由3个项(2的幂)组成，并且设置的位数也等于3.

where 0 <= a < ... < n are integers, and A, ..., N are either zeroes, or ones. If we remove the zero-product terms, the number of terms will be equal to the number of set bits (ones). For example, 1101_b = 2⁰ + 2² + 2³ consists of three terms (powers of two), and the number of set bits is also equal to three.

想法是在此表示形式中找到非零项的数量.

The idea is to find the number of non-zero terms in this representation.

如果我们将u表示为两个幂的和:

If we express u as a sum of powers of two:

u = 2ª + ... + 2ⁿ

其中0 <= a < ... < n，则整数除法u = u / 2可以表示为:

where 0 <= a < ... < n, then the integer division u = u / 2 can be expressed as:

u = ( 2ª + ... + 2ⁿ ) / 2

或等效地:

u = ( 2ª / 2 ) + ... + ( 2ⁿ / 2 )

(通常是(x + y) / 2 = (x / 2) + (y / 2).)

在u为正时重复该过程.因此，每个术语最终等于一个.在下一次迭代中，由于整数除法规则，它变为等于零:1 / 2 = 0.

The process is repeated while u is positive. So each term eventually becomes equal to one. In the next iteration it becomes equal to zero due to the rules of integer division: 1 / 2 = 0.

从存储在foo:foo -= u中的原始值中减去结果值(u).

The resulting value (u) is subtracted from the original value stored in foo: foo -= u.

因此，我们最终从原始值foo中减去了所有内容，除了一分二"(1 / 2).

Thus, we eventually subtract everything from the original value foo, except the "ones divided by two" (1 / 2).

很明显，1 / 2的出现次数等于u原始表达式中的非零项次数，它等于置位位数(如上所述).因此，剩余的值"n foo"是剩余的"1 / 2"的总和，即项数也是设置位数.

Obviously, the number of occurrences of 1 / 2 is equal to the number of non-zero terms in the original expression of u which is equal to the number of set bits (as we found out above). Hence, the value remaining ìn foo is a sum of "1 / 2" leftovers, i.e. the number of terms which is also the number of set bits.

让我们以u = 13为例对过程进行可视化.

Let's visualize the process on example of u = 13.

十进制数字13的二进制表示形式是1101.因此，十进制表示法的2的幂次加和为:

Binary representation of the decimal number 13 is 1101. So the sum of powers of two in decimal notation is:

u = 2⁰ + 2² + 2³

第一次迭代:

u = u / 2
  = (2⁰ + 2² + 2³) / 2
  = (2⁰ / 2) + (2² / 2) + (2³ / 2)
  = 0        + 2        + 2²

到目前为止，我们有一个零:2⁰ / 2 = 1 / 2 = 0.

We have one zero so far: 2⁰ / 2 = 1 / 2 = 0.

第二次迭代:

u = u / 2
  = (2      + 2²) / 2
  = (2 / 2) + (2² / 2)
  = 1       + 2

在此迭代中不再有零.第三次迭代:

No more zeroes in this iteration. Third iteration:

u = u / 2
  = (1      + 2) / 2
  = (1 / 2) + (2 / 2)
  = 0       + 1

在此迭代中，我们得到了第二个零:1 / 2 = 0.

We have got the second zero in this iteration: 1 / 2 = 0.

第四次迭代给出了第三个零:

Fourth iteration gives the third zero:

u = u / 2
  = 1 / 2 = 0.

零的个数等于置位的个数，即3.

The number of zeroes is equal to the number of set bits, i.e. 3.

这篇关于为什么此函数计算整数中设置的位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！