(This question refers to this Codeforces problem)
I want to find out if any n (2 ≤ n ≤ 10¹⁴) has an odd divisor or not. Using C++11, I thought it would be possible to brute force a solution by iterating through every odd number until n, and checking with % if it is divisible or not. Something such as:
for(unsigned long long i=3;i<n;i+=2){
if(n%i==0) return true; //It has an odd divisor
}
return false; //n%j==0 was never true so it doesn't have an odd divisor
Which of course turned out to be extremely slow if any big number were given. I found out people were solving it by bit-shifting it, and checking if the last bit was 1, something similar to this:
while(!(n&1))n>>=1;
if(n==1) return false; else return true;
If I am not mistaken, this last piece of code is checking if it's odd with the last bit (n&1) by performing n=n/2ⁿ.
How does computing n=n/2ⁿ have the same accuracy in regards solving the problem as checking it for every odd number? (How do I know that I am not ''skipping'' a divisor?).
To understand this, you have to understand how rightmost bit of odd and even number works.
Basically any odd number has it's 0th bit(rightmost) as 1(remember bit counting start from right, i.e right most bit is 0th bit, then you go left one by one i.e 1st bit, 2nd bit and so on) and any even number has it's 0th bit as 0.
so when you do
int value = n & 1;
what are you doing is that you are doing 'AND' of n & 1, so if the n is odd, then it's 0th bit will be 1, so when you do suppose for example
int result = 5 & 1;
now this actually look like this
(101) & (001)
so you get 1 as a result(since all other bits of 1 are 0, so the result of AND of all those other bits of 5 & 1 will be 0, so basically you remain with 1), but if n is even, then it's 0th bit will be 0, for example
int result = 10 & 1;
will look like this
1010 & 0001
now based on previous example, you can see that the result will be always be 0 in case of even numbers. This is why checking if a number is odd or even is much faster this way as you don't go in all modulo and other higer level stuff, you are doing stuff in low level here.
So coming to the main point, what is happening is that we have to check if a number contains any odd divisor or not, let us see it step by step
A number is a nothing but multiple of it's divisors, for example
30 = 10 * 3;
30 = 15 * 2;
30 = 5 * 6
but if you will look closer, you will find that it is always a combination of same unique prime numbers i.e
30 = 2 * 5 * 3;
30 = 3 * 5 * 2;
30 = 5 * 2 * 3;
So now let's see a fact among prime number, we see that 2 is the only prime number that is not odd.
If we go with this fact, we can be sure if 2 is multiplied by any other prime number , then that resultant number will always be an odd number(and remember even * odd = odd).
so if we want a number that doesn't have any odd divisors, then we don't want any odd prime number in it's multiplication combination, then that number should be combination of 2's multiplication only, in other terms power of 2. (we can ignore case of 1, as it is provided in the problem to not consider that as input)
so If we just a check a number if it's is a power of 2 or not, our problem is solved, i.e if it is power of 2, then it doesn't contain any odd divisor, else it contain a odd divisor.
now how do we find if a number is a power of 2 or not.
so any number we see can be a combination of different bit in it's binary representation
for example
10 = (1010) (2^3 * 1 + 2^2 * 0 + 2^1 * 1 + 2^0 * 0)
if any number is a just power of 2, then it will have only single bit as 1 in it's binary representation, all other bits will be 0 ( for case of 2^0 = 1 , you can see that we have been given constraint that x > 1, so we can ignore case handling for 1)
so now let's look at this code
// it runs the while loop until all the right bits of first 1 bit is 0, that is it runs till we shift our rightmost 1 bit to 0th bit
while(!(n & 1)) {
n >>= 1; // if we are inside the loop, it means rightmost 1 is still not at 0th bit position, as the AND is done for 0th bit like I explained above, so doing this will right shift our rightmost 1, i.e if it was at 2nd position, it will now come at 1st position
}
if(n == 1) {
// if it is 1, it means only 1 bit is there in whole binary representation of the number which is at 0th position, it means it is a power of two(remember that this n is calculated based on sum of all the power of 2)
return false;
} else {
return true;
}