title: Count ones in a segment (binary)
body: <p>There is a problem which i am working on it right now and it's as follows :</p>
  
  <p>there are two numbers x1 and x2 and x2 > x1.</p>
  
  <p>for example x1 = 5; and x2 = 10;</p>
  
  <p>and I must find the sum of ones between x1 and x2 in binary representations.</p>
  
  <pre><code>5 = 101   =&gt; 2 ones
  6 = 110   =&gt; 2 ones
  7 = 111   =&gt; 3 ones
  8 = 1000  =&gt; 1 one
  9 = 1001  =&gt; 2 ones
  10= 1010  =&gt; 2 ones
  so the sum will be 
  sum = 2 + 2 + 3 + 1 + 2 + 2 = 12 ones;
  </code></pre>
  
  <p>so I have managed to do the code without even transfer the numbers to binary and wasting execution time.</p>
  
  <p>I noticed that the numbers of ones in every <code>2^n</code> with <code>n &gt;= 1</code> is <code>1</code>
  Ex : <code>2^1 =&gt; num of ones is 1</code>
  <code>2^2  =&gt;  1</code> <code>2^15  =&gt; 1</code></p>
  
  <p>you can test it here if you want:  <a href="https://www.rapidtables.com/convert/number/decimal-to-binary.html?x=191" rel="nofollow noreferrer">https://www.rapidtables.com/convert/number/decimal-to-binary.html?x=191</a> </p>
  
  <p>and between each <code>2^n and 2^(n+1)</code> there are Consecutive numbers as you will see in this example :</p>
  
  <pre><code>      num              number of ones
  2^4 = 16                      1
        17                      2
        18                      2
        19                      3
        20                      2
        21                      3
        22                      3
        23                      4
        24                      2
        25                      3
        26                      3
        27                      4
        28                      3
        29                      4
        30                      4
        31                      5
  2^5 = 32                      1
  </code></pre>
  
  <p>so I did a code that can find how many ones between <code>2^n and 2^(n+1)</code></p>
  
  <pre><code>int t;                ////turns
  int bin = 1;              //// numbers of ones in the binary format ,,, and 1 for 2^5
  int n1 = 32;          //// 2^5  this is just for clarification 
  int n2 = 64;          //// 2^6
  int *keep = malloc(sizeof(int) * (n2 - n1);             ///this is to keep numbers because 
                                        /// i'll need it later in my consecutive numbers
  int i = 0;
  int a = 0;
  n1 = 33               //// I'll start from 33 cause "bin" of 32 is "1";
  
  while (n1 &lt; n2)       /// try to understand it now by yourself
  {
      t = 0;
      while (t &lt;= 3)
      {
  
          if (t == 0 || t == 2) 
              bin = bin + 1;
  
          else if (t == 1) 
              bin = bin;
  
          else if (t == 3)
          {
              bin = keep[i];
              i++;
          }
          keep[a] = bin;
          a++;
          t++;
      }
      n1++;
  }
  </code></pre>
  
  <p>anyway as you see I am close to solve the problem but they give me huge numbers and i must find the ones between them, unfortunately I have tried a lot of methods to calculate the "sum" using this code above and I end up with Time executing problem.<br>
  Ex: <code>1, 1000000000   the numbers of ones is &gt;&gt;&gt; 14846928141</code></p>
  
  <p>so can you give me a little hint what to do next, thanx in advance.</p>
  
  <p>I'm doing this for a code war challenge: <a href="https://www.codewars.com/kata/596d34df24a04ee1e3000a25/train/c" rel="nofollow noreferrer">https://www.codewars.com/kata/596d34df24a04ee1e3000a25/train/c</a></p>