Last_Of_UsOO's blog

Count Set Bit !!
By Last_Of_UsOO, history, 21 month(s) ago, In English

Can the set bit be counted at each position throughout the range [L, R]? 1 <= L, R <= 10^12

Example : [5, 13]

5:    101
6:    110
7:    111
8:   1000
9:   1001
10:  1010
11:  1011
12:  1100
13:  1101

0th position : 5 1st position : 4 2nd position : 5 3rd position : 6

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
21 month(s) ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

I think we can using digit dp on binary representation of number

→ Reply
»
21 month(s) ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Digit Dp and maybe Gray code can be used. https://www.geeksforgeeks.org/what-is-gray-code/

→ Reply
  • »
    »
    21 month(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    #include<bits/stdc++.h>
#define ll long long
using namespace std;

ll solve( ll bit , ll n )
{
        ll powr = ( 1ll << bit );
        if( powr > n )
        return 0;

	ll repeat = n / ( powr * 2 ) ;
	ll mod = n % ( powr * 2 );
	ll tot = repeat*powr;
	tot += max(0ll,mod-powr);
	return tot;
}

signed main()
{
    ll l,r;
    cin>>l>>r;

    // r <= 1e12
    vector<ll>set_bits(41,0);

    for( ll p = 0 ; ( 1ll << p ) <= r ; p++ )
    set_bits[p] = solve(p,r+1) - solve(p,l);
    
}
    → Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Use the fact that the bits at ith position alternate after every 2^i numbers. So for a bit i, find the first number after L which has it set call it L_set, and first number below L which has it un-set called it L_unset this can be done in constant time. Similarly do it for R also, now that you know the range — [L_unset+1, R_unset-1] has a multiple of 2^i numbers and you know L_unset, L_set, R_unset and R_set you can subtract the out of range elements from this count.

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For i. bit,

$$$f(X)$$$ will give count of numbers in $$$1 \leq y \leq X$$$

You can see the contrubition pattern is $$$i$$$ number of 0s, $$$i$$$ number of 1s, $$$i$$$ number of 0s, etc.

So if $$$X$$$ equals $$$2^{(i + 1)} \times y$$$, count is $$$2^i \times y$$$

Else, divide it into 2 parts: $$$2^{(i + 1)} \times y$$$, and another part, $$$Z$$$, which is in $$$0 \leq Z \le 2^{(i + 1)}$$$, and the first part calculation is the same.

We can say for another part their contrubition pattern is $$$i$$$ numbers of 0 and $$$i$$$ number of 1. (Not any more)

If it is smaller than $$$2^i$$$, its contribution is 0

Else its contrubition is $$$Z - 2^i$$$

And answer for i. bit is $$$f(R) - f(L - 1)$$$

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I recently created a video on this topic. I also created a practice problem. You can submit your code here

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This stack overflow link might be helpful -> Stack overflow question

→ Reply