trjhtr

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?

• 
  

  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.

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