如何将一个数除3而不使用*、/、+、-、%等运算符?

号码可以有签名,也可以没有签名。


当前回答

使用fma()库函数的解决方案,适用于任何正数:

#include <stdio.h>
#include <math.h>

int main()
{
    int number = 8;//Any +ve no.
    int temp = 3, result = 0;
    while(temp <= number){
        temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
        result = fma(result, 1, 1);
    } 
    printf("\n\n%d divided by 3 = %d\n", number, result);
}

请看我的另一个答案。

其他回答

这是经典的2进制除法算法

#include <stdio.h>
#include <stdint.h>

int main()
{
  uint32_t mod3[6] = { 0,1,2,0,1,2 };
  uint32_t x = 1234567; // number to divide, and remainder at the end
  uint32_t y = 0; // result
  int bit = 31; // current bit
  printf("X=%u   X/3=%u\n",x,x/3); // the '/3' is for testing

  while (bit>0)
  {
    printf("BIT=%d  X=%u  Y=%u\n",bit,x,y);
    // decrement bit
    int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
    uint32_t r = x>>bit;  // current remainder in 0..5
    x ^= r<<bit;          // remove R bits from X
    if (r >= 3) y |= 1<<bit; // new output bit
    x |= mod3[r]<<bit;    // new remainder inserted in X
  }
  printf("Y=%u\n",y);
}

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;

使用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
}

愚蠢的情况需要愚蠢的解决方案:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE * fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char * buf = calloc(number,1);
    fwrite(buf,number,1,fp);
    rewind(fp);
    int result=fread(buf,divisor,number,fp);
    printf("%d / %d = %d", number, divisor, result);
    free(buf);
    fclose(fp);
    return 0;
}

如果还需要小数部分,只需将result声明为double,并将fmod(number,除数)的结果添加到它。

解释它是如何工作的

fwrite写入number字节(在上面的例子中number为123456)。 “倒带”将文件指针重置到文件的前面。 Fread从文件中读取长度为除数的最多数量的“记录”,并返回它所读取的元素的数量。

如果你写30个字节,然后以3为单位读回文件,你会得到10个“单位”。30 / 3 = 10