Hello!

Tomorrow is an important day for me and I promised to myself that I will just chill all the day before, you know in order to keep the mind clean and fresh.. But.. I found this interesting problem and you know what, let’s work it out đź™‚

The problem is: You’re given two numbers reppresented in 2’s complement notation:Â *a* and *bÂ *where –*2^31,<=a<=b<=2^31-1*, and you’re asked to calculate the amount of bits set to 1 you may encounter when reading the binary rappresentation of all the numbers from *a* to *b* (inclusive).

So for example, if a=0 and b=7 then f(a,b)=12. If you count: 000, 001, 010, 011, 100, 101, 110 ,111 and sum all the one’s then you get 12. Since we are dealing with 2’s complement representation then one must remember that for example -1 is ~1+1, so basically it have 32 ones..Â LINKÂ for details đź™‚

The brute force approach is just to loop from *a* to *b *summing theÂ hamming weight of all the numbers, since we can perform the calculation in O(1) and we’re going to loop potentially from -2^31 to 2^31-1 (some 4 billions iteration) well, the performance is going to be a nightmare! Well, O(n) is not really so bad everywhere else, but here we really want to do better.

Anyway, the brute force code is the following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int bit_count(long n) { n = n - ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); return (((n + (n >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } ll brute_force(long a,long b) { ll ans{0}; while(a<=b) { ans += bit_count(a); ++a; } return ans; } |

*bit_countÂ *calculate the hamming weight for the given number n. That’s all. Now let’s solve the very same problem doing some analysis first:

Here we have all the numbers from 0 to 15, now notice that the rightmost column (8-15) is identical to the left column but each number has one additional 1 (MSB), in the same way the numbers from 4-7 have the same amount of bits that the one from 0 to 3 but with one additional MSB. And so on..

Seems we have a pattern, now we need to notice one more thing:Â Look just a the left column and count the number of bits set to 1 in each subcolumn, you’ll notice that each subcolumn has 4 bits set.

The only exception is the first subcolumn which has only 0. But still, if you count all the 1 the you get 12! How many subcolumn do we have? Well, looks like we have exactlyÂ *k=log2(n)* for each *n=2^k-1*, this hold also for n=15 which is *2^4-1* and have 4 subcolumn. Please note that 0..7 has 4 bit in each subcolumn, and *0..15* has 8 bit in each subcolumn, or justÂ *2^(k-1)*Â .

So basically to calculate the amount of bits set to 1 in ALL the numbers between 0 and* 2^k-1* all we need to do is: *k*2^(k-1)*. But what if n is not a power of 2?? Let’s pick 12, and let’s notice the solution for n=12 we have:

- For sure it will have more than k*
*2^(k-1)*Â bits set, where*k=floor(log2(n)), as we already have seen before.* - n-2^k is the amount of numbers for which we need to calculate the amount of bits, which is 4 for n=12, and here we can exploit the first thing we have noticed from the table, the bit pattern between 0..4 and 8..12 is exacly the same for the first 3 leftmost subtables!
- Now we miss only the additional 1 appearing from 8 to 12, we have
*n+1-2^k*of them

Nasty huh?? The solution is *f(n)=k*2^(k-1)+f(n-2^k)+(n-2^k+1)*, with *Â f(1)=1 * and *f(n<=0)=0*. To calculate the number of bits betweenÂ *aÂ *andÂ *b* we just can perform *f(b)-f(a-1)* (remember that *a,b* inclusive) and were are done.

But what about negative numbers? This is easy, since is sufficient to note that in 2’s complements theÂ amount of bits set betweenÂ *-5* and *0* is the same as from f(*2^31-1) –*Â f(*2^31-1-abs(-1)) + abs(-5)Â *or in general: *f(2^31-1)-f(2^31-1-abs(n))+abs(n)*. Let’s call this lastÂ *fn,Â *like f for negative. If *a<0 and b>0* the clearly the solution isÂ *fn(a)+f(b). Â (*You may spot this equivalence by writing on paper -1,-2,-3 etc).

Here is finally the code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
using ll = long long; constexpr long mx = 2147483647; //2^31-1 ll mpow(long n,long p) { if(p<0) return 0; ll r{1}; while(p-->0) r*=n; return r; } long calc_positive(long n) { if(n==1) return 1; if(n<=0) return 0; long x = log2(n); long p = mpow(2,x-1); return x*p + calc_positive(n-p*2) + (n-p*2+1); } long calc_negative(long n) { return (calc_positive(mx) - calc_positive(mx - abs(n))+ abs(n)); } int main() { long n; ll ans{0}; cin >> n; n*=2; vector data(n); for(long i{0};i<n;i++) cin>>data[i]; if(data.size()%2!=0) { cerr<<"This is not good!n"; } else { for(ll i{0};i<data.size();i+=2) { long a = data[i]; long b = data[i+1]; if(a>=0 && b>=0) { cout<<(calc_positive(b)-calc_positive(a-1))<<endl; } else if(a<=0 && b<0) { cout<<calc_negative(a) - calc_negative(b+1)<<endl; } else if(a=0) { cout<<calc_negative(a) + calc_positive(b)<<endl; } } } return 0; } |

And if you feed the code with the following input:

5

0 561651

-5616511 85545

-21154844 -22115

321 65816351

0 0

You’ll get:

5295748

118605035

422810617

851696046

0

you may check the correctness of the code by using the brute force approach, but remember, the brute force approach is way more slower, the claver implementation is O*(log2(n)).Â *No matter how many number we have betweenÂ *a *andÂ *b,Â *the amount of steps is virtually the same.

Thanks for reading đź™‚