Determine if the solution to a division is odd or even

Question

Is there a way to quickly determine if the solution to a division operation will be odd or even? I need a quick way determine that in a program. Doing a complete a complete division takes up too much time.

Here is something that is known beforehand:

• both numbers are even
• there is no remainder
• in $a/b$, b is not $2^n$

I tried to look into patterns in their binary representations to no avail. Currently what I have is

isOdd = (a / b) & 1;  //pseudocode

but dividing two big numbers is just too expensive.

Answer 1

You have the numbers in binary form already? Then just compute $ord_2$ of $a$ and $b$. Here, $ord_2(n)$ denotes the greatest power of $2$ which divides $n$. Thus $ord_2(5)=0$, $ord_2(24)=3$, and so on. You can read this off from the binary forms...$ord_2(n)$ is the number of zeros before the first one in the binary representation (reading from right to left). Thus $$ord_2(10111011000)=3$$ To solve your problem, note that the quotient $\frac ab$ will be even if and only if $ord_2(a)>ord_2(b)$.

Answer 2

if a is even then a = $2^n*a'$ for some odd a'. b is even so b = $2^m*b'$. So a/b = $2^{n-m}(a/b)$ which is even if n > m but odd if n = m.

Answer 3

C-style code:

/* Assumes b!=0 and a divisible by b */
bit_index = 1
while (b&bit_index==0) {
  if (a & bit_index) { /* Error, a is not divisible by b; odd over even */ }
  bit_index = bit_index >> 1
}
return (a&bit_index)>0