logo标签列表

在一个范围内的整数的二进制补码表示中1的数量

algorithmbinaryrecurrence
15
这个问题来自于2011 Codesprint (http://csfall11.interviewstreet.com/)：
计算机科学的基础之一是了解数字在二进制补码中的表示方法。假设你使用32位的二进制补码，写下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个1。 对于第二个测试用例，答案是31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99。
我意识到可以利用“-X的1的数量等于(-X)的补码的0的数量=X-1”的事实来加速搜索。解决方案声称存在一个O(log X)的递归关系来生成答案，但我不理解它。可以在这里查看解决方案代码: https://gist.github.com/1285119 如果有人能解释一下这个关系是如何推导出来的，我将不胜感激！
可能是重复的问题：找到从1到n的所有集合位的总数 - 只需使用该公式两次即可找到F(B) - F(A)。 - BlueRaja - Danny Pflughoeft
http://en.wikipedia.org/wiki/Two's_complement - djangofan
4个回答
31

嗯，其实并不是那么复杂...

单参数的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（包括a）中所有整数中1的位数。

该函数有三种情况：

a == 0 -> 返回0。 很明显。

a是偶数-> 返回a的1位数加上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++中整数除法会向下取整。）

对于第一组数，它们的最后一位都是0；而对于第二组数，它们的最后一位都是1。因此，这些最后一位共有(a+1)/2个1位。

所以，递归的第三种情况是(a+1)/2 + 2*solve(a/2)，需要对a进行long long类型转换，以便处理a为INT_MAX（因此a+1会溢出）的情况。

这是一个O(log N)的解法。要将其推广到solve(a,b)，只需计算solve(b) - solve(a)，并添加适当的逻辑来处理负数即可。这就是带两个参数的solve(int a, int b)函数所做的事情。

谢谢你的解释，@Nemo，你的说明很有道理！ - pdsouza
这段代码的作用是什么 __builtin_popcount(a) ?? - nikhil
3
这是一个GCC内置函数，用于计算整数中1的位数。 - Nemo
你想在最后一段使用 solve(b) - solve(a-1) 而不是 solve(b) - solve(a) 吗？ - Mark Dickinson
3
将数组转换为一系列整数。然后针对每个整数执行以下操作：
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位整数中设置位的数量？

2

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

如果a为负数，在32位系统上，从a到0之间的每个负数都将比从0到正数a的二进制表示中的位数少32个1的位数范围内的数字多。

因此，更好的表述是：

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);
    }
}
1
在以下代码中，x的位和被定义为0到x（包括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的公式为：

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

请注意，x - 2 ^ i = x & (2 ^ i)-1。
负数与正数处理略有不同。在这种情况下，零的数量从总位数中减去：
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;
        }
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接