某个范围内整数的二进制补码表示形式中 1 的数量

Question

这个问题来自2011年的Codesprint（http://csfall11.interviewstreet.com/）：

基础知识之一计算机科学的核心是了解数字如何用 2 的补码表示。想象一下，您使用 32 位以 2 的补码表示形式写下了 A 和 B 之间的所有数字（包括 A 和 B）。你总共会写下多少个 1 ？ 输入： 第一行包含测试用例的数量 T (<1000)。接下来的 T 行中的每一行都包含两个整数 A 和 B。 输出： 输出 T 行，每个测试用例对应一条。 限制条件： -2^31 <= A <= B <= 2^31 - 1

示例输入： 3 -2 0 -3 4 -1 4 示例输出： 63 99 37

解释： 对于第一种情况，-2 包含 31 个 1，后跟 0，-1 包含 32 个 1，0 包含 0 个 1。因此总数为 63。 对于第二种情况，答案是 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我意识到你可以利用 -X 中 1 的数量等于 -X 中 0 的数量这一事实(-X) = X-1 的补码可加快搜索速度。该解决方案声称存在 O(log X) 递归关系来生成答案，但我不明白它。解决方案代码可以在这里查看： https://gist.github.com/1285119

我将不胜感激如果有人能解释一下这个关系是如何导出的！

Answer 1

嗯，这并没有那么复杂...

单参数的solve(int a) 函数是关键。它很短，所以我将它剪切并粘贴到这里：

long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}

它仅适用于非负 a，并且它计算从 0 到 a 的所有整数（包括 0 和 a）中 1 位的数量。

该函数有三种情况：

a == 0 ->返回 0。显然。

a 偶数 ->返回 a 加上 solve(a-1) 中 1 的位数。也相当明显。

最后一个案例很有趣。那么，我们如何统计从 0 到奇数 a 中 1 位的个数呢？

考虑 0 到 a 之间的所有整数，并将它们分为两组：偶数和奇数。例如，如果 a 为 5，则有两个组（二进制）：

000  (aka. 0)
010  (aka. 2)
100  (aka. 4)

并

001  (aka 1)
011  (aka 3)
101  (aka 5)

观察这两个组必须具有相同的大小（因为 a 是奇数，并且范围是包容性的）。要计算每组中有多少个 1 位，请首先计算除最后位之外的所有位，然后计算最后位。

除了最后几位之外的所有内容都看起来像这样：

00
01
10

...对于两个组来说都是这样。这里1的位数就是solve(a/2)。 （在此示例中，它是从 0 到 2 的 1 位的数量。另外，请记住 C/C++ 中的整数除法向下舍入。）

对于第一组中的每个数字，最后一位都是零第二组中的每个数字对应一个，因此最后几位为总数贡献 (a+1)/2 一位。

因此，递归的第三种情况是 (a+1)/2 + 2*solve(a/2)，并适当转换为 long long 来处理以下情况： a 是 INT_MAX（因此 a+1 溢出）。

这是一个 O(log N) 的解决方案。要将其推广为 solve(a,b)，您只需计算 solve(b) -solve(a)，加上用于处理负数的适当逻辑。这就是双参数 solve(int a, int b) 所做的事情。

Answer 2

将数组转换为一系列整数。然后对于每个整数执行以下操作：

int NumberOfSetBits(int i)
{
   i = i - ((i >> 1) & 0x55555555);
   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
   return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

这也是可移植的，与 __builtin_popcount 不同

请参见此处：如何计算 32 位整数中设置的位数？

Answer 3

当 a 为正时，更好的解释已经发布。

如果 a 为负数，则在 32 位系统上，a 和 0 之间的每个负数将有 32 个 1 位，减去从 0 到正 a 的二进制表示范围内的位数。

所以，以更好的方式，

long long solve(int a) {
    if (a >= 0){
        if (a == 0) return 0;
        else if ((a %2) == 0) return solve(a - 1) + noOfSetBits(a);
        else return (2 * solve( a / 2)) + ((long long)a + 1) / 2;
    }else {
        a++;
        return ((long long)(-a) + 1) * 32 - solve(-a);
    }
}

Answer 4

在以下代码中，x 的位和定义为 0 到 x（含）之间数字的二进制补码表示形式中 1 位的计数，其中 Integer.MIN_VALUE <= x <= Integer.MAX_VALUE。

例如：

bitsum(0) is 0   
bitsum(1) is 1   
bitsum(2) is 1   
bitsum(3) is 4

..etc

10987654321098765432109876543210 i % 10 for 0 <= i <= 31
00000000000000000000000000000000 0
00000000000000000000000000000001 1
00000000000000000000000000000010 2
00000000000000000000000000000011 3
00000000000000000000000000000100 4
00000000000000000000000000000101 ...
00000000000000000000000000000110
00000000000000000000000000000111 (2^i)-1
00000000000000000000000000001000  2^i
00000000000000000000000000001001 (2^i)+1 
00000000000000000000000000001010 ...
00000000000000000000000000001011 x, 011 = x & (2^i)-1 = 3
00000000000000000000000000001100
00000000000000000000000000001101
00000000000000000000000000001110
00000000000000000000000000001111
00000000000000000000000000010000
00000000000000000000000000010001
00000000000000000000000000010010 18
...
01111111111111111111111111111111 Integer.MAX_VALUE

位和的公式为：

bitsum(x) = bitsum((2^i)-1) + 1 + x - 2^i + bitsum(x & (2^i)-1 )

注意 x - 2^i = x & (2^i)-1

负数的处理方式与正数略有不同。在这种情况下，从总位数中减去 0 的数量：

Integer.MIN_VALUE <= x < -1
Total number of bits: 32 * -x.

负数 x 中 0 的数量等于 -x - 1 中 1 的数量。

public class TwosComplement {
    //t[i] is the bitsum of (2^i)-1 for i in 0 to 31.
    private static long[] t = new long[32];
    static {
        t[0] = 0;
        t[1] = 1;
        int p = 2;
        for (int i = 2; i < 32; i++) {
            t[i] = 2*t[i-1] + p;
            p = p << 1;
        }
    }

    //count the bits between x and y inclusive
    public static long bitsum(int x, int y) {
        if (y > x && x > 0) {
            return bitsum(y) - bitsum(x-1);
        }
        else if (y >= 0 && x == 0) {
            return bitsum(y);
        }
        else if (y == x) {
            return Integer.bitCount(y);
        }
        else if (x < 0 && y == 0) {
            return bitsum(x);
        } else if (x < 0 && x < y && y < 0 ) {
            return bitsum(x) - bitsum(y+1);
        } else if (x < 0 && x < y && 0 < y) {
            return bitsum(x) + bitsum(y);
        }
        throw new RuntimeException(x + " " + y);
    }

    //count the bits between 0 and x
    public static long bitsum(int x) {
        if (x == 0) return 0;
        if (x < 0) {
            if (x == -1) {
                return 32;
            } else {
                long y = -(long)x;
                return 32 * y - bitsum((int)(y - 1));
            }
        } else {
            int n = x;
            int sum = 0;     //x & (2^i)-1
            int j = 0;
            int i = 1;       //i = 2^j
            int lsb = n & 1; //least significant bit
            n = n >>> 1;
            while (n != 0) {
                sum += lsb * i;
                lsb = n & 1;
                n = n >>> 1;
                i = i << 1;
                j++;
            }
            long tot = t[j] + 1 + sum + bitsum(sum);
            return tot;
        }
    }
}