Count total set bits

Question

Im am solving Count total set bits:

Find the sum of all bits from numbers 1 to N.

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N.

Output:

Print the sum of all bits.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 1000

Example:

Input:
2
4
17

Output:
5
35

Explanation:
An easy way to look at it is to consider the number, n = 4:
0 0 0 = 0
0 0 1 = 1
0 1 0 = 1
0 1 1 = 2
1 0 0 = 1
Therefore , the total number of bits is 5.

My approach:

/*package whatever //do not write package name here */

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

class GFG {
    private static int noOfBits (int N)
        {
            int sum = 0;
            for (int i = 1; i <= N; i++)
                {
                    if ((i & i-1) == 0)
                        {
                            sum += 1;
                        }
                    else
                        {
                            sum += numBits(i);
                        }
                }
            return sum;
        }

    private static int numBits (int num)
        {
            int sum = 0;
            int rem;
            while (num != 0)
                {
                   rem = num%2;
                   num /= 2;
                   sum += rem;
                }
            return sum;
        }

    public static void main (String[] args) throws IOException {
        //code
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        String line = br.readLine();
        int T = Integer.parseInt(line);
        String line2;
        int N;

        for (int i = 0; i < T; i++)
            {
                line2 = br.readLine();
                N = Integer.parseInt(line2);
                System.out.println(noOfBits(N));
            }
    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

2. Is there a better way to solve this question?

3. Are there any grave code violations that I have committed?

4. Can space and time complexity be further improved?

Answer 1

• Your way of indenting and placing braces is consistent, which is good. I prefer the K&R style, which is also recommended in the (historical) Java Code Conventions from Sun Microsystems, or the Google Style Guides:

  • Open brace “{” appears at the end of the same line as the declaration statement
  • Closing brace “}” starts a line by itself indented to match its corresponding opening statement, ...

• You have separated the I/O from the actual computation, which is again good, as it keeps the main method short, and allows to add unit tests more easily.

• Reading the input can be simplified slightly by using Scanner.

• Short (nondescriptive) variable names T and N are usually not recommended. In this case it might be acceptable, since those names correspond directly to the identifiers used in the programming challenge description.

  However, it is not immediately apparent what the method names noOfBits and numBits stand for, and what distinguished them. A better choice could be totalSetBits (corresponding to the challenge description), and countBits, plus short explaining comments.

• I am not sure if the special treatment of powers of 2 in if ((i & i-1) == 0) is worth the additional code, as it applies only to few numbers in the range 1...N. In any case, it should be part of the numBits() method.

• The separate variable int rem in numBits() is not needed.

Summarizing the suggestions so far, the code would look like this:

import java.io.IOException;
import java.util.Scanner;

class GFG {

    // Total count of all 1 bits in the binary representation of the
    // numbers 1 ... N.
    private static int totalSetBits(int N) {
        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += countBits(i);
        }
        return sum;
    }

    // Number of 1 bits in the binary representation of n.
    private static int countBits(int n) {
        if ((n & n-1) == 0) {
            return 1; // n is a power of 2.
        }
        int count = 0;
        while (n != 0) {
            count += n % 2;
            n /= 2;
        }
        return count;
    }

    public static void main (String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 1; i <= T; i++) {
            int N = scanner.nextInt();
            int bits = totalSetBits(N);
            System.out.println(bits);
        }
    }
}

How can we make this faster? One approach would be to make countBits() faster, and you'll find various methods to count the number of set bits in an integer at Bit Twiddling Hacks.

But perhaps we can compute totalSetBits(N) better than adding countBits(n) for all numbers n from 1 to N? This is the real challenge here, and I don't want to deprive you from the satisfaction of figuring out the solution yourself, so here are some hints only:

First have a look at some special values:

0
1  --> totalSetBits(1) = 1

00
01
10
11 --> totalSetBits(3) = 2 * 2 = 4

000
001
...
110
111 -> totalSetBits(7) = 3 * 4 = 12

Can you spot the general pattern?

Then try compute totalSetBits(N) for arbitrary N by using those “special values.” This should lead to a \$ O(\log N) \$ solution instead of the current \$ O( N) \$ solution.

And of course – when not in an interview – you can “cheat:” Compute totalSetBits(N) for the first (e.g.) 40 values of N, and look up the resulting sequence in the On-Line Encyclopedia of Integer Sequences®. For many programming challenges, this leads to useful information and insights into the problem.

Answer 2

In my opinion, the best code is always the code you don't need to write. Thus, the "better" solution for real life is simply knowing the java library and using it.

In this case for any n:

BitSet.valueOf(LongStream.rangeClosed(1, n).toArray()).cardinality()