Java 在数字范围内计算一位

Question

我在计算大量范围内的一位时遇到问题。

所以我必须在 1 到 1000 的 eq 数范围内计算一位这是4938。

public static long countRangeOneBits(long n){
    long t = 0;
    for (long i = 1; i <= n; i++) {
        long x = i;
        while (x > 0) {
            t += x%2;
            x /= 2;
        }
    }
    return t;
}

好的，这工作正常，但我需要计算范围 1..10^16。首先，Java不会计算那么大的数字，至少对于长数据类型。我还有其他选择吗，或者你们对我应该如何处理这个问题有任何提示。

| From 1 To        | Total             |
|                1 |                1  |
|               10 |               14  |
|              100 |              319  |
|             1000 |             4938  |
|            10000 |            64613  |
|           100000 |           815030  |
|          1000000 |          9884999  |
|         10000000 |        114434632  |
|        100000000 |       1314447116  |
|       1000000000 |      14846928141  |
|  100000000000000 | 2306412649693200  |
| 1000000000000000 |24784747400675300  |

Answer 1

我想

你需要玩 2^n。作为从 0 到 （2^n - 1） = n * 2^（n-1） 的 1 位总数。

在程序中，这就是您想要的

private static long getBits(long l){
        if(l == 0){
            return 0;
        }else if(l == 1){
            return 1;
        }
        boolean isPowerOf2Minus1 = (l & (l+1)) == 0;
        long maxBitNum = Long.highestOneBit(isPowerOf2Minus1 ? l+1 : l);
        int maxBit = Long.numberOfTrailingZeros(maxBitNum);
        if((l & (l+1)) == 0){
            return maxBit * (maxBitNum >> 1);
        }
        long diff = l - maxBitNum;
        return diff + 1 + getBits(maxBitNum - 1) + getBits(diff);
    }

结果如下

                   1 :                    1
                  10 :                   17
                 100 :                  319
                1000 :                 4938
               10000 :                64613
              100000 :               815030
             1000000 :              9884999
            10000000 :            114434632
           100000000 :           1314447116
          1000000000 :          14846928141
         10000000000 :         164293127179
        100000000000 :        1809725656079
       1000000000000 :       19809942118413
      10000000000000 :      214309466746894
     100000000000000 :     2306412649693201
    1000000000000000 :    24784747400675348
   10000000000000000 :   264286863212871700
  100000000000000000 :  2804216299269586964

Answer 2

由于您需要使用如此多的数字来执行此操作，因此查找表可能是最简单的方法：

final int TABLE_SIZE = 65536;
int[] table = new int[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; ++i)
  table = hammingWeight(i);

然后，您可以将数字分成 16 位块，并将它们的所有权重相加以计算结果，因为汉明权重可以计算为起始数字两部分的权重之和，例如：

long number = 12445235;
int weight = table[number & 0xFFFF] + table[(number >>> 16) & 0xFFFF];

当然，您必须找到一种方法来指定比long数据类型长的数字，但这应该不会太难，只需关心符号和移位即可。

Answer 3

您可以使用

// this turns into a single machine instruction
int numOfBitSet = Long.bitCount(n);

这将计算为最大 9 * 10^18 的值设置的位数。

Answer 4

对于 2 的幂

countRangeOneBits（n） = 2 * countRangeOneBits（n/2） + （n/2）

解释：如果你有一个数字表作为位，后半部分只有右边一个位（n/2 个额外的位）。

所以 10^16 应该可以用长头来做。

更多细节我不能凭良心提供。

Answer 5

对于范围 0..2^n-1，对于某些 n，每个数字都可以用 n 位表示，在整个范围内，对于恰好一半的数字，给定位将为 0，另一半将为 1。例如，0..7为您提供 000、001、010、011、100、101、110、111，其中四个数字的每个位为 0，其中四个数字的每个位为 1。因此，所有八个数字的汉明权重之和是 2 n*ⁿ/2，这里是 8*3/2 或 12。

因此，计算从 0 到 9007199254740992（2 的最大幂小于 10¹⁶）的总和是相当微不足道的。

获得最后992800745259008值更难......您可以通过从每个值中减去9007199254740992并重复上述过程来递归地计算它们，但为每个值加 1 以表示您减去的9007199254740992。