[aisowner]

i'm wondering if there's any theorem or just any easy way to check
if the product of 2 8 bit numbers is divisible by 6 using just bit operators? no *(product) or /(divide) or modulus operation allowed.

i'm currently checking if either one can be divided by two and other by three or if one of them can be divided by two and three.

[mgweir]

You can check divisibility by two using a shift operation and checking the smallest bit of the product. If that bit is true/1, the product is not divisible by two. I'm not so sure that the divisibility by three can be checked faster than a mod/divide operation. Try playing around with various shift operations and see what you can get.
mgweir

[mccoyn]

As you probally know you can easily check if a base 10 number is divisible by 9 by adding the digits and determining if the result is divisible by 9 (possibly recursively.) This is true because 9+1 = 10. The same relationship exists in other bases. Of use to us is base 4. 3+1 = 4, so all we have to do is look at the number in base 4 (easy enough) and add up the digits. If the result is a multiple of 3, the original number is divisible by 3.

Code:

bool divisible_by_3(unsigned char x){
  while (x > 3){
    x = ((x & (0x03 << 0))  >> 0)
      + ((x & (0x03 << 2))  >> 2)
      + ((x & (0x03 << 4))  >> 4)
      + ((x & (0x03 << 6))  >> 6);
  }
  return (x == 3;)
}

This might be slower than modulating, but it uses only bit operations and addition.

Checking for divisible by 2 is much easier. It is just a bitwise and operation.

Code:

bool divisible_by_2(unsigned char x){
  return (x & 0x01) == 0;
}