Math Is Fun Forum

AV

Guest

mod of 3

You are given a number n and you have to find if its divisble by 3 but the catch is you cant use mod or division operations
i am looking for something using binary arithmetic

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,711

Re: mod of 3

I recall using integer division in the past. It had special methods that may suit you.

Now if I could only find what I did with it ....

... I did find this: http://www.bearcave.com/software/divide.htm , the author has some C code that might do it for you.

The central part of his code has:

  while (remainder < divisor) {
    bit = (dividend & 0x80000000) >> 31;
    remainder = (remainder << 1) | bit;
    d = dividend;
    dividend = dividend << 1;
    num_bits--;
  }

(he says that always goes one step too far, so he just backs up once.)

Is that what you were looking for?

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman