CODEWITHSUNDEEP
c++algorithm
techriften
techriften

Reputation: 421

what will be the common factor in 2 numbers.?

Ingenerally we find common factors between two numbers say 8 and 12 as 4. But in programming language,i want to find the common number when both the numbers are divided by 2. We divide both numbers by 2 and check for the common number Like for numbers 8 and 11 8->4->2 11->5->2 hers we get 2 as the common number. I want to implement it efficiently for numbers upto 10^9. Hers is my implementation

long long i,j;
while(i!=1||j!=1)
{
    i=i/2;
    j=j/2;
    if(i==j)
    flag=1;
    break;
}

but i and j will be same at different times.How to implement that?

Upvotes: 2

Views: 1386

Answers (2)

fredoverflow
fredoverflow

Reputation: 263118

i want to find the common number when both the numbers are divided by 2

Your question is kinda vague. I assume you want to find the greatest common dividing power of 2?

Powers of 2 can easily be detected in binary due to their trailing zeros:

  1    00000001
  2    00000010
  4    00000100
  8    00001000
 16    00010000
 32    00100000
 64    01000000
128    10000000

All numbers that have a single 2 in their prime factorization have exactly one trailing zero:

  2    00000010    2
  6    00000110    2*3
 10    00001010    2*5
 14    00001110    2*7
 18    00010010    2*3*3

You can do the same for multiples of 4, 8, 16 and so on and will come to the conclusion that you can detect the powers of 2 in a number by the number of trailing zeros in its binary representation.

Multiples of 2 (that are not multiples of 4) will end in 10, multiples of 4 (that are not multiples of 8) will end in 100 and so on. The bits before that rightmost 1 are not interesting to us.

So what we want to do is isolate that rightmost 1 bit. Fortunately, there is a nice bit trick for that:

int rightmost_bit(int x)
{
    return x & -x;
}

How does this work? If you look at the binary representation of x and -x in twos complement, they only share a single 1 bit, namely the rightmost, which is exactly the one we are interested in:

           *
 40    00101000
-40    11011000
&          *
  8    00001000

All bits to the right of the rightmost bit of x are also 0 in -x, and all bits to the left of -x are the opposite of those in x, hence they cancel each other out when combining them with binary-and.

A naive approach to finding the greatest common dividing power of 2 would hence be:

int gcd_p2_naive(int a, int b)
{
    return std::min(rightmost_bit(a), rightmost_bit(b));
}

But we can do even better with another simple bit trick, one that I just came up with:

int gcd_p2(int a, int b)
{
    return rightmost_bit(a | b);
}

Why does this work? I will leaven this open as an exercise for the reader ;)

Upvotes: 2

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

You can do this in a bit more complex logic - use two numbers and always divide the greater of them:

int get(int a, int b) {
  while (a != b) {
    if (a < b) {
      swap(a, b);
    }
    a /= 2;
  }
  return a;
}

Explanation: eventually any positive integer when divided by two will get to 1 so the cycle will terminate for sure and this will happen at worst when both a and b are 1. On each step I make sure that a is not less than b and then I divide it by 2.

Upvotes: 4

Related Questions