提问



如果不使用*/+-%,运算符,你如何将数字除以3?


号码可以是签名或未签名。

最佳参考


这是一个执行所需操作的简单功能。但它需要+运算符,所以你要做的只是用位运算符添加值:[95]


// replaces the + operator
int add(int x, int y)
{
    while (x) {
        int t = (x & y) << 1;
        y ^= x;
        x = t;
    }
    return y;
}

int divideby3 (int num)
{
    int sum = 0;
    while (num > 3) {
        sum = add(num >> 2, sum);
        num = add(num >> 2, num & 3);
    }
    if (num == 3)
        sum = add(sum, 1);
    return sum; 
}


正如吉姆评论的那样,因为:



  • n = 4 * a + b

  • n / 3 = a + (a + b) / 3

  • So sum += a, n = a + b,并迭代

  • a == 0 (n < 4)sum += floor(n / 3);即1,if n == 3, else 0


其它参考1


白痴状况需要一种愚蠢的解决方案:


#include 
#include 

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,divisor)的结果添加到其中。


解释它是如何工作的



  1. fwritenumber个字节(上例中的数字为123456)。

  2. rewind将文件指针重置为文件的前面。

  3. fread从文件中读取最长numberdivisor长度divisor,并返回它读取的元素数。



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

其它参考2


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

其它参考3


#include 
#include 

int main(int argc, char *argv[])
{

    int num = 1234567;
    int den = 3;
    div_t r = div(num,den); // div() is a standard C function.
    printf("%d\n", r.quot);

    return 0;
}

其它参考4


您可以使用(平台相关的)内联汇编,例如,对于x86 :(也适用于负数)[96]


#include 

int main() {
  int dividend = -42, divisor = 5, quotient, remainder;

  __asm__ ( "cdq; idivl %%ebx;"
          : "=a" (quotient), "=d" (remainder)
          : "a"  (dividend), "b"  (divisor)
          : );

  printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
  return 0;
}

其它参考5


使用itoa转换为基数3字符串。删除最后一个trit并转换回基数10. [97] [98]


// 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
}

其它参考6


(注意:请参阅下面的编辑2以获得更好的版本!)


这并不像听起来那么棘手,因为你说不使用[[..]] + [[..]] 运算符。如果您想禁止同时使用+字符,请参阅下文。


unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    for (unsigned i = 0; i < by; i++)
      cmp++; // that's not the + operator!
    floor = r;
    r++; // neither is this.
  }
  return floor;
}


然后只是说div_by(100,3)100除以3





修改:您可以继续并替换++运算符:



unsigned inc(unsigned x) {
  for (unsigned mask = 1; mask; mask <<= 1) {
    if (mask & x)
      x &= ~mask;
    else
      return x & mask;
  }
  return 0; // overflow (note that both x and mask are 0 here)
}





编辑2:稍微快一点的版本,不使用任何包含+-*/% 字符的运算符的



unsigned add(char const zero[], unsigned const x, unsigned const y) {
  // this exploits that &foo[bar] == foo+bar if foo is of type char*
  return (int)(uintptr_t)(&((&zero[x])[y]));
}

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    cmp = add(0,cmp,by);
    floor = r;
    r = add(0,r,1);
  }
  return floor;
}


我们使用add函数的第一个参数,因为我们不能在不使用*字符的情况下表示指针的类型,除了函数参数列表,其中语法type[]与[[type[]相同。 78]]。


FWIW,您可以使用类似的技巧轻松实现乘法功能,以使用AndreyT提出的0x55555556技巧:


int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}

其它参考7


在Setun计算机上很容易实现。[100]


要将整数除以3,请向右移1位。[101]


我不确定是否真的可以在这样的平台上实现一致的C编译器。我们可能不得不稍微延长规则,比如将至少8位解释为能够保持至少从-128到+127的整数。

其它参考8


这是我的解决方案:


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 + ...


现在我们所要做的就是将这些位移值加在一起!哎呀!我们不能添加,所以相反,我们必须使用逐位运算符编写一个add函数!如果你熟悉逐位运算符,我的解决方案应该看起来相当简单......但是如果你不是这样的话,我将在最后介绍一个例子。


另外需要注意的是,首先我向左移动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,我们得到了错误的答案。

其它参考9


因为它来自Oracle,所以预先计算出答案的查找表怎么样。:-D

其它参考10


要将32位数除以3,可将其乘以0x55555556,然后取64位结果的高32位。


现在剩下要做的就是使用位操作和移位来实现乘法......

其它参考11


又一个解决方案。这应该处理除int的最小值之外的所有整数(包括负整数),这需要作为硬编码异常处理。这基本上通过减法除法,但仅使用位运算符(shift,xor,&和补码)。为了更快的速度,它减去3 *(减少2的幂)。在c#中,它每毫秒执行大约444个DivideBy3调用(1,000,000个分频为2.2秒),所以不是非常慢,但没有像简单的x/3那样快。相比之下,Coodey的漂亮解决方案比这个快5倍。


public static int DivideBy3(int a) {
    bool negative = a < 0;
    if (negative) a = Negate(a);
    int result;
    int sub = 3 << 29;
    int threes = 1 << 29;
    result = 0;
    while (threes > 0) {
        if (a >= sub) {
            a = Add(a, Negate(sub));
            result = Add(result, threes);
        }
        sub >>= 1;
        threes >>= 1;
    }
    if (negative) result = Negate(result);
    return result;
}
public static int Negate(int a) {
    return Add(~a, 1);
}
public static int Add(int a, int b) {
    int x = 0;
    x = a ^ b;
    while ((a & b) != 0) {
        b = (a & b) << 1;
        a = x;
        x = a ^ b;
    }
    return x;
}


这是c#,因为这是我的方便,但与c的差异应该是次要的。

其它参考12


这真的很容易。


if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;


(为了简洁,我当然省略了一些程序。)如果程序员厌倦了全部输入,我确信他或她可以编写一个单独的程序来为他生成它。我碰巧要知道某个操作员,/,这将极大地简化他的工作。

其它参考13


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


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


执行模数函数也很容易,检查注释。

其它参考14


这是基数2中的经典除法算法:


#include 
#include 

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<= 3) y |= 1<

其它参考15


int div3(int x)
{
  int reminder = abs(x);
  int result = 0;
  while(reminder >= 3)
  {
     result++;

     reminder--;
     reminder--;
     reminder--;
  }
  return result;
}

其它参考16


用Pascal编写程序并使用DIV运算符。


由于问题标记为c,您可以在Pascal中编写一个函数并从C程序中调用它;这样做的方法是系统特定的。/questions/tagged/c


但这是一个可以在我的Ubuntu系统上安装Free Pascal fp-compiler软件包的示例。(我这样做是出于完全错位的固执;我没有声称这是有用的。)


divide_by_3.pas :


unit Divide_By_3;
interface
    function div_by_3(n: integer): integer; cdecl; export;
implementation
    function div_by_3(n: integer): integer; cdecl;
    begin
        div_by_3 := n div 3;
    end;
end.


main.c :


#include 
#include 

extern int div_by_3(int n);

int main(void) {
    int n;
    fputs("Enter a number: ", stdout);
    fflush(stdout);
    scanf("%d", &n);
    printf("%d / 3 = %d\n", n, div_by_3(n));
    return 0;
}


构建:


fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main


示例执行:


$ ./main
Enter a number: 100
100 / 3 = 33

其它参考17


没有交叉检查这个答案是否已经发布。如果程序需要扩展到浮动数字,数字可以乘以10 *所需的精度数,然后再次应用以下代码。


#include 

int main()
{
    int aNumber = 500;
    int gResult = 0;

    int aLoop = 0;

    int i = 0;
    for(i = 0; i < aNumber; i++)
    {
        if(aLoop == 3)
        {
           gResult++;
           aLoop = 0;
        }  
        aLoop++;
    }

    printf("Reulst of %d / 3 = %d", aNumber, gResult);

    return 0;
}

其它参考18


这适用于任何除数,而不仅仅是三个。目前仅用于未签名,但将其扩展为签名应该不那么困难。


#include 

unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do      {
        one = ~two & bor;
        two ^= bor;
        bor = one<<1;
        } while (one);
return two;
}

unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;

if (!bot || top < bot) return 0;

for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;

for (result=0; shift--; bot >>= 1 ) {
        result <<=1;
        if (top >= bot) {
                top = sub(top,bot);
                result |= 1;
                }
        }
return result;
}

int main(void)
{
unsigned arg,val;

for (arg=2; arg < 40; arg++) {
        val = bitdiv(arg,3);
        printf("Arg=%u Val=%u\n", arg, val);
        }
return 0;
}

其它参考19


使用eval和字符串连接在幕后使用/运算符会不会是作弊?


例如,在Javacript,你可以做到


function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}

其它参考20


在PHP中使用BC Math:[103] [104]








MySQL (这是甲骨文的采访)[105]


> SELECT 12345 DIV 3;





帕斯卡: [106]


a:= 12345;
b:= a div 3;





x86-64汇编语言:


mov  r8, 3
xor  rdx, rdx   
mov  rax, 12345
idiv r8

其它参考21


首先,我想出了。


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


编辑:抱歉,我没有注意到标签C。但你可以使用关于字符串格式化的想法,我猜......

其它参考22


以下脚本生成一个C程序,无需使用运算符* / + - %即可解决问题:


#!/usr/bin/env python3

print('''#include 
#include 
const int32_t div_by_3(const int32_t input)
{
''')

for i in range(-2**31, 2**31):
    print('    if(input == %d) return %d;' % (i, i / 3))


print(r'''
    return 42; // impossible
}
int main()
{
    const int32_t number = 8;
    printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')

其它参考23


使用黑客的Delight Magic数字计算器 [107]


int divideByThree(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}


其中fma是math.h标题中定义的标准库函数。[108]

其它参考24


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


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

其它参考25


我认为正确的答案是:


为什么我不使用基本操作员进行基本操作?

其它参考26


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


#include 
#include 

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);
}


看到我的另一个答案。

其它参考27


使用cblas,作为OS X的加速框架的一部分。[111]


[02:31:59] [william@relativity ~]$ cat div3.c
#import 
#import 

int main() {
    float multiplicand = 123456.0;
    float multiplier = 0.333333;
    printf("%f * %f == ", multiplicand, multiplier);
    cblas_sscal(1, multiplier, &multiplicand, 1);
    printf("%f\n", multiplicand);
}

[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031

其它参考28


第一:


x/3 = (x/4) / (1-1/4)


然后弄清楚如何解决x/(1 - y):


x/(1-1/y)
  = x * (1+y) / (1-y^2)
  = x * (1+y) * (1+y^2) / (1-y^4)
  = ...
  = x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
  = x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))


y=1/4:


int div3(int x) {
    x <<= 6;    // need more precise
    x += x>>2;  // x = x * (1+(1/2)^2)
    x += x>>4;  // x = x * (1+(1/2)^4)
    x += x>>8;  // x = x * (1+(1/2)^8)
    x += x>>16; // x = x * (1+(1/2)^16)
    return (x+1)>>8; // as (1-(1/2)^32) very near 1,
                     // we plus 1 instead of div (1-(1/2)^32)
}


虽然它使用+,但有人已经通过按位运算实现了add

其它参考29


好吧,我想我们都同意这不是一个现实世界的问题。所以只是为了好玩,这里是如何用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;