检查一个数字是否可以被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;
}

Answer 2

减去3直到你

a)命中0 - 数字可被3整除

b)得到一个小于0的数字 - 数字不可分割

- 编辑版本以修复已发现的问题

while n > 0:
    n -= 3
while n < 0:
    n += 3
return n == 0

Answer 3

将数字拆分为数字.将数字加在一起.重复,直到只剩下一位数字.如果该数字为3,6或9,则该数字可被3整除.(并且不要忘记将0作为特殊情况处理).

Answer 4

虽然转换为字符串然后将十进制数字加在一起的技术很优雅,但它要么需要除法,要么在转换为字符串步骤中效率低下.有没有办法直接将这个想法应用于二进制数,而不首先转换为十进制数字串？

事实证明,有:

给定二进制数,如果原始数字可被3整除,则其奇数位的总和减去其偶数位的总和可被3整除.

例如:取数字3726,它可被3整除.在二进制中,这是111010001110.所以我们取奇数,从右边开始向左移动,它们是[1,1,0,1,1,1]; 这些的总和是5.偶数位为[0,1,0,0,0,1]; 这些的总和是2.5 - 2 = 3,我们可以从中得出结论,原始数字可以被3整除.

Answer 5

一个可被3整除的数字,iirc具有一个特征,即其数字的总和可被3整除.例如,

12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9

Answer 6

面试问题基本上要求你提出(或者已经知道)可分性规则的简写,以3作为除数.

3的可分性规则之一如下:

取任意数字并将数字中的每个数字加在一起.然后取出该总和并确定它是否可被3整除(重复相同的程序).如果最终数字可以被3整除,那么原始数字可以被3整除.

例:

16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.

也可以看看

• 维基百科/可分性规则 - 对许多除数有很多规则

Answer 7

给出一个数字x.将x转换为字符串.逐字符解析字符串.将每个已解析的字符转换为数字(使用atoi())并将所有这些数字加到新的数字y中.重复此过程,直到最终结果数字为一位数.如果该一个数字是3,6或9,则原始数字x可被3整除.

Answer 8

我的Java解决方案仅适用于32位无符号 int s.

static boolean isDivisibleBy3(int n) {
  int x = n;
  x = (x >>> 16) + (x & 0xffff); // max 0x0001fffe
  x = (x >>> 8) + (x & 0x00ff); // max 0x02fd
  x = (x >>> 4) + (x & 0x000f); // max 0x003d (for 0x02ef)
  x = (x >>> 4) + (x & 0x000f); // max 0x0011 (for 0x002f)
  return ((011111111111 >> x) & 1) != 0;
}

它首先将数字减少到小于32的数字.最后一步通过将掩码向右移动适当的次数来检查可分性.