division - 检查一个数是否能被3整除

Question

我需要在不使用 %、/ 或 * 的情况下判断一个数字是否能被 3 整除。给出的提示是使用atoi()函数。知道该怎么做吗？

Answer 1

当应用“将所有数字相加，看看是否能除以 3”时，当前答案都集中在十进制数字上。这个技巧实际上也适用于十六进制；例如0x12 可以除以 3，因为 0x1 + 0x2 = 0x3。并且“转换”为十六进制比转换为十进制要容易得多。

伪代码:

int reduce(int i) {
  if (i > 0x10)
    return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
  else
   return i; // Done.
}
bool isDiv3(int i) {
  i = reduce(i);
  return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}

[编辑]受 R 启发，更快的版本 (O log log N):

int reduce(unsigned i) {
  if (i >= 6)
    return reduce((i >> 2) + (i & 0x03));
  else
   return i; // Done.
}
bool isDiv3(unsigned  i) {
  // Do a few big shifts first before recursing.
  i = (i >> 16) + (i & 0xFFFF);
  i = (i >> 8) + (i & 0xFF);
  i = (i >> 4) + (i & 0xF);
  // Because of additive overflow, it's possible that i > 0x10 here. No big deal.
  i = reduce(i);
  return i==0 || i==3;
}