Java Counting one bits in number range

Question

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  |

I am fairly confident that there's a pattern there that would allow you to "count" bits without enumerating every possibility. — Hot Licks
– Hot Licks, Commented Dec 31, 2013 at 16:45
No, but school extra programming assignment. I just need some help in ways to approach this problem. — Jompper
– Jompper, Commented Dec 31, 2013 at 16:45
Maybe you should post this to the Math board... But if you do want to do this the bruteforce way: Use BigInteger, you can represent any whole number with that (As long as you have enough memory...). — Sibbo
– Sibbo, Commented Dec 31, 2013 at 16:45

DKSRathore · Accepted Answer · 2013-12-31 20:48:30Z

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

Jack · Accepted Answer · 2013-12-31 17:08:54Z

1

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.

answered Dec 31, 2013 at 17:08

Jack

134k33 gold badges252 silver badges349 bronze badges

Comments

Peter Lawrey · Accepted Answer · 2013-12-31 17:37:47Z

1

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.

answered Dec 31, 2013 at 17:37

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

1 Comment

user41871 Over a year ago

+1 Generally useful answer. But I suspect that the instructor wouldn't accept it. :-)

Joop Eggen · Accepted Answer · 2013-12-31 18:21:16Z

0

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.

answered Dec 31, 2013 at 18:21

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

Comments

dcsohl · Accepted Answer · 2013-12-31 20:47:46Z

For the range 0..2ⁿ-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 2ⁿ*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 10¹⁶) 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.

Collectives™ on Stack Overflow

Java Counting one bits in number range

5 Answers 5

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related