Can anyone explain the approach of the below question
https://www.codechef.com/COOK113A/problems/XORIT
If N is a power of 2, then A=B=1.
Else, A is the smallest set bit of N. For example, if N = 11010, then A = 10 and B = 11000.
We can then use some math to count for each bit i, the number of N such that the smallest bit of N is i, then we can use more math to find the answer.
Wow Your code is so clean.
I got the idea but implementation took quite some time . Iām so bad at bit manupulationā¦
yeah basically the function F(n) is n&(n1) if (n&(n1)_!=0 else 1 but how to find sum , please elaborate more
This is my algorithm.
 Count the sum of all numbers from L to R
 Now A is minimum as the rightmost set bit, if N = 101010 then A = 10, if contains only one active bit then its 1. So we just need count of numbers having ith bit as LSB (least significant bit)
You can do this
Check number of last 1 bits after right shifting L and R
And that is reduced to count of odd numbers only  Keep doing this for every bit and reduce them from overall total and you get your answer
My code for reference: Link
Sum of B = Sum of (NA) = Sum of N  Sum of A
Sum of N is easy to find (n*(n+1)/2 formula).
Sum of A can be found by iterating through all i and adding up 2^i * (count of numbers having bit i as the smallest bit).
Also, you need to consider N=2^i independently since A=B=1 in that case.
After doing some math ā¦ I did not do āmore mathā.
can someone please tell me whatās wrong in my solution??
I would say my algo is really simple. You can observe that B is N after removing the least significant bit. If there is only one least significant bit, then B = 1 as B cannot be 0. So, you take sum of all integers from 1 to N, that is (N * (N + 1)) / 2. You subtract the (2 ^ number of trailing zeroes) for each number. This can be proved to be (floor(n / 1) * 1 + floor(n / 2) * 1 + floor(n / 4) * 2 + floor(n / 8) * 4 + floor(n / 16) * 8 +ā¦). You have the sum now which is sum of all integers from 1 to N with (2 ^ number of trailing zeroes) subtracted from each of them. But we have missed one case, where B = 0. B is zero only when N is a power of 2. So we need to subtract (log2(N) + 1) from our sum as B = 0 is treated as B = 1. This will give the correct answer.
From a person whose bio tells me that he doesnāt like maths
There are problems with much worse math
This problem is just a few simple formulas
How are we talking in terms of āsumā, when the operation mentioned is XOR? Please clarify, thanks!
Okay, what do we know about the XORoperation? Some basic properties include:
 \oplus is a binary relation, \oplus: S \times S \rightarrow S,where\ S = \{0, 1\}

A \oplus 0 = A, where\ A \in S summarized as:
\textbf{zero is the identity element for } \oplus.  A \oplus B = 0 \Longleftrightarrow A = B, where\ A, B \in S, summarized as: \textbf{every element is its own inverse for } \oplus
Notice that the identity element for both \oplus and + is zero, which means when we add and xor two binary numbers (as xor deals only in zeroes and ones), we get the same output at positions where at least one of the two numbers is unset (has a 0). The only combination of that remains to be taken care of is when both operands (or positions in those numbers) are set. While xor nullifies them (since one is the inverse of the other for xor), the sum goes on to generate a carry (which do give the same output at the current position for the two operations but which changes their overall output).
Finally, in this problem, we never have a situation where a position is set in both A and B implying that the results of sum and xor of the two will be the same, and thus we can exploit this fact to ease our calculations. The proof as to why this is true is wellexplained in the editorial
Could you please explain how this formula gives us the required count of numbers having ind bit as set bit !
ct = ((r >> ind) / 2) + ( (r >> ind) % 2)  (((l1) >> ind) / 2)  (((l1) >> ind) % 2);