3以2为底等于11。

所以只要做长除法(就像中学那样)，以2 × 11为底。以2为底比以10为底更简单。

对于从最有效位开始的每个位位:

判断prefix是否小于11。

如果它是输出0。

如果不是输出1，则替换前缀位进行适当的更改。只有三种情况:

 11xxx ->    xxx    (ie 3 - 3 = 0)
100xxx ->   1xxx    (ie 4 - 3 = 1)
101xxx ->  10xxx    (ie 5 - 3 = 2)

所有其他前缀都不可达。

重复到最低位，你就完成了。

好吧，我想我们都同意这不是一个现实世界的问题。为了好玩，这里是如何用Ada和多线程来做这件事:

with Ada.Text_IO;

procedure Divide_By_3 is

   protected type Divisor_Type is
      entry Poke;
      entry Finish;
   private
      entry Release;
      entry Stop_Emptying;
      Emptying : Boolean := False;
   end Divisor_Type;

   protected type Collector_Type is
      entry Poke;
      entry Finish;
   private
      Emptying : Boolean := False;
   end Collector_Type;

   task type Input is
   end Input;
   task type Output is
   end Output;

   protected body Divisor_Type is
      entry Poke when not Emptying and Stop_Emptying'Count = 0 is
      begin
         requeue Release;
      end Poke;
      entry Release when Release'Count >= 3 or Emptying is
         New_Output : access Output;
      begin
         if not Emptying then
            New_Output := new Output;
            Emptying := True;
            requeue Stop_Emptying;
         end if;
      end Release;
      entry Stop_Emptying when Release'Count = 0 is
      begin
         Emptying := False;
      end Stop_Emptying;
      entry Finish when Poke'Count = 0 and Release'Count < 3 is
      begin
         Emptying := True;
         requeue Stop_Emptying;
      end Finish;
   end Divisor_Type;

   protected body Collector_Type is
      entry Poke when Emptying is
      begin
         null;
      end Poke;
      entry Finish when True is
      begin
         Ada.Text_IO.Put_Line (Poke'Count'Img);
         Emptying := True;
      end Finish;
   end Collector_Type;

   Collector : Collector_Type;
   Divisor : Divisor_Type;

   task body Input is
   begin
      Divisor.Poke;
   end Input;

   task body Output is
   begin
      Collector.Poke;
   end Output;

   Cur_Input : access Input;

   -- Input value:
   Number : Integer := 18;
begin
   for I in 1 .. Number loop
      Cur_Input := new Input;
   end loop;
   Divisor.Finish;
   Collector.Finish;
end Divide_By_3;

以下是我的解决方案:

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时，我们得到错误的答案。

使用itoa转换为以3为基数的字符串。去掉最后一个小调，转换回10进制。

// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
    char str[42];
    sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
    if (i>0)                     // Remove sign if positive
        str[0] = ' ';
    itoa(abs(i), &str[1], 3);    // Put ternary absolute value starting at str[1]
    str[strlen(&str[1])] = '\0'; // Drop last digit
    return strtol(str, NULL, 3); // Read back result
}

你可以考虑用图或树状结构来解决这个问题。基本上生成的顶点数与要除以3的数一样多。然后继续将每个未配对的顶点与其他两个顶点配对。

粗糙的伪代码:

function divide(int num)
    while(num!=0)
        Add a new vertice to vertiexList.
        num--
    quotient = 0
    for each in vertexList(lets call this vertex A)
        if vertexList not empty
            Add an edge between A and another vertex(say B)
        else
            your Remainder is 1 and Quotient is quotient
        if vertexList not empty
            Add an edge between A and another vertex(say C)
        else
            your remainder is 2 and Quotient is quotient
        quotient++
        remove A, B, C from vertexList
    Remainder is 0 and Quotient is quotient

这显然是可以优化的，复杂度取决于你的数字有多大，但它应该工作，只要你能做++和——。 这就像数更酷的东西一样。

首先是我想到的。

irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub('   ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222

编辑:对不起，我没有注意到标签c。但是你可以使用字符串格式的想法，我猜…