Let Us Understand Computer

Mr. ABC was recently learning about computer division. Considering the basic model of the computer suppose we wish to divide a number X by D i.e X/D and obtain the result (Note that it is integer division i.e result of 7/2 will be 3).

Now the computer will give the divide overflow error if:

The number of bits in the binary representation(without appending any leading zeroes) of the resulting number(quotient) is greater than the number of bits in the binary representation of divisor(D) (Without appending any leading zeroes).

Example:

Input:  n = 3
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long bit(long long n)
{
    long long cnt = 0;
    while (n)
    {
        cnt++;
        n = n & (n - 1);
    }
    return cnt;
}

long long understandComputer(long long n)
{

    long long ans = 0;
    long long i = 1;
    while (i <= sqrt(n))
    {
        i = i * 2;
        if (n / i >= i / 2)
            ans = n - n / i;
        else
            ans = n - i / 2 + 1;
    }
    return ans;
}
int main()
{

    long long n = 3;

    cout << understandComputer(n) << "\n";

    return 0;
}