-5

How can I count "1" digits in binary representation of a numbers from a to b.

Where 0 < a <= b < 10^16.

James Rodrigues
  • 107
  • 10
  • @πάνταῥεῖ ῥεῖ How? Can you explain? – James Rodrigues Mar 21 '15 at 08:16
  • @James Rodrigues AFAIK there is no integral type in C++ and C that can contain values 10 ^16.:) So a question arises what type of the object that contains the binary representations of such big numbers and what type of the numbers themselves? – Vlad from Moscow Mar 21 '15 at 08:22
  • >there is no integral type in C++ and C that can contain values 10 ^16 < Unless you create one in C++, and overload tons of operators for it. – myaut Mar 21 '15 at 08:46

1 Answers1

1

To find solution of the task P[a..b], you have to find solutions for subproblems P[0..b] and P[0..a] and subtract these values.
Now consider P[0..x] task. Simple case x=2^k (100..000bin).

0th bit is set in 2^k/2 numbers (it alternates every time)
1th bit is set in 2^k/2 numbers (it alternates after pair of numbers)
..
k-1th bit is set in 2^k/2 numbers (in 2^(k-1)..(2^k)-1))
kth bit is set in one number (in 2^k)

So 

P[0..2^k] = k * 2^(k-1) + 1

To find solution for arbitrary x, we can exploit binary representation of x, for example:
P(1010b) = P(1000b) + P(10b)

pseudocode

P = 0
k = 0 
while x <> 0 do
   if (x and 1) then //check if kth bit is set in x
       P = P + k * 2^(k-1) + 1 
   x = x >> 1  //shift right
   k = k + 1
MBo
  • 77,366
  • 5
  • 53
  • 86