以下是我的解决方案:

public static int div_by_3(long a) {
    a <<= 30;
    for(int i = 2; i <= 32 ; i <<= 1) {
        a = add(a, a >> i);
    }
    return (int) (a >> 32);
}

public static long add(long a, long b) {
    long carry = (a & b) << 1;
    long sum = (a ^ b);
    return carry == 0 ? sum : add(carry, sum);
}

首先，请注意

1/3 = 1/4 + 1/16 + 1/64 + ...

现在，剩下的很简单!

a/3 = a * 1/3  
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...

现在我们要做的就是把a的这些位移位值加在一起!哦!但是我们不能做加法，所以我们必须使用位操作符来编写一个加法函数!如果您熟悉逐位操作符，那么我的解决方案应该看起来相当简单……但以防你不懂，我会在最后讲一个例子。

另一件需要注意的事情是，首先我左移30!这是为了确保分数不会四舍五入。

11 + 6

1011 + 0110  
sum = 1011 ^ 0110 = 1101  
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100  
Now you recurse!

1101 + 0100  
sum = 1101 ^ 0100 = 1001  
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000  
Again!

1001 + 1000  
sum = 1001 ^ 1000 = 0001  
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000  
One last time!

0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17  
carry = (0001 & 10000) << 1 = 0

Done!

这就是你小时候学过的简单加法!

111
 1011
+0110
-----
10001

这个实现失败了，因为我们不能把方程的所有项相加:

a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i

假设div_by_3(a) = x的结果，则x <= floor(f(a, i)) < a / 3。当a = 3k时，我们得到错误的答案。

log(pow(exp(number),0.33333333333333333333)) /* :-) */

这在Setun电脑上很容易实现。

要把一个整数除3，右移1位。

不过，我不确定在这样的平台上是否有可能实现一个符合标准的C编译器。我们可能需要稍微扩展一下规则，比如将“至少8位”解释为“能够保存至少从-128到+127的整数”。

并不是所有的答案都是面试官想听到的:

我的回答:

“我绝不会那样做，谁会为这种愚蠢的事情付出代价呢?”没有人 会有一个优势，它不是更快，它只是愚蠢。 教授设计师必须知道这一点，但这必须适用于所有数字，而不仅仅是除以3。”

使用计数器是一个基本的解决方案:

int DivBy3(int num) {
    int result = 0;
    int counter = 0;
    while (1) {
        if (num == counter)       //Modulus 0
            return result;
        counter = abs(~counter);  //++counter

        if (num == counter)       //Modulus 1
            return result;
        counter = abs(~counter);  //++counter

        if (num == counter)       //Modulus 2
            return result;
        counter = abs(~counter);  //++counter

        result = abs(~result);    //++result
    }
}

也很容易执行一个模数函数，查看注释。

这个方法(c#)怎么样?

private int dividedBy3(int n) {
        List<Object> a = new Object[n].ToList();
        List<Object> b = new List<object>();
        while (a.Count > 2) {
            a.RemoveRange(0, 3);
            b.Add(new Object());
        }
        return b.Count;
    }