Last_Of_UsOO's blog

Count Set Bit !!
By Last_Of_UsOO, history, 4 hours 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
  • +6
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you Implement it !!.

    → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You Can Take Help From this

They Explain all way to explain this problem.

→ Reply
»
3 hours ago, # |
← 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
  • »
    »
    2 hours ago, # ^ |
      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
»
3 hours ago, # |
  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
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So I've to find every first number that is set at ith index and then count the 2^i time.

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no pre-computing is required we can do that at every query for L and R as it takes constant time, that's better imo

      → Reply
»
3 hours ago, # |
  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
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro it's hard to be understand can you simplify it.

    → Reply
    • »
      »
      »
      68 minutes ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      It is about contribution pattern.

      Example if we consider i=1, pattern is like 0011 0011 0011 0011...

      So you need only count 1s in this pattern

      → Reply