CODEWITHSUNDEEP
javabinarybit
Jompper
Jompper

Reputation: 1402

Java Counting one bits in number range

I have a problem counting one bits in a large number ranges.

So I have to count one bits in a eq number range from 1 to 1000 which is 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;
}

Ok this works fine, but I need to calculate range 1..10^16. First of all java won't count that big numbers, at least with long data type. Do I have any other options or do you guys have any tips on how I should approach this problem.

| 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  |

Upvotes: 3

Views: 1087

Answers (5)

DKSRathore
DKSRathore

Reputation: 3063

I guess you need to play with 2^n. As total number of 1 bits from 0 to (2^n - 1) = n * 2^(n-1).

And in programs this is what you want

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);
    }

With below results

                   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

Upvotes: 1

dcsohl
dcsohl

Reputation: 7406

For the range 0..2n-1, for some n, each number can be expressed with n bits, and over that entire range, for exactly half of the numbers a given bit will be 0, and it will be 1 for the other half. For example, 0..7 gives you 000, 001, 010, 011, 100, 101, 110, 111 and each bit is 0 for four of those numbers and 1 for four of those numbers. Ergo, the sum of the hamming weights for all eight numbers is 2n*n/2, which here is 8*3/2 or 12.

So calculating your sum from 0 to 9007199254740992 (the largest power of two less than 1016) is quite trivial.

Getting those last 992800745259008 values is harder... you could probably recursively figure them out by subtracting 9007199254740992 from each value and repeating the above process but add 1 for each of them to represent the 9007199254740992 you subtracted.

Upvotes: 0

Joop Eggen
Joop Eggen

Reputation: 109567

For powers of 2

countRangeOneBits(n) = 2 * countRangeOneBits(n / 2) + (n / 2)

Explanation: if you have a table of numbers as bits, the second half just has one bit to the right (n/2 extra bits).

So 10^16 should be doable with a long.

More details I cannot with good conscience deliver.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533560

You can use

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

This will count the number of bits set for values up to 9 * 10^18.

Upvotes: 1

Jack
Jack

Reputation: 133597

Since you need to do it with so many numbers probably a lookup table would be the easiest way to go:

final int TABLE_SIZE = 65536;
int[] table = new int[TABLE_SIZE];

for (int i = 0; i < TABLE_SIZE; ++i)
  table = hammingWeight(i);

Then you could just split your number in 16 bits chunks and sum all their weights together to compute the result, since the hamming weight can be computed as the sum of the weights of two parts of the starting number, eg:

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

Of course you'll have to find a way to specify numbers that are longer than a long data type but it shouldn't be too difficult, just care about sign and shifts.

Upvotes: 1

Related Questions