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

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


当前回答

第一:

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。

其他回答

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)

所有其他前缀都不可达。

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

我认为正确的答案是:

为什么不用基本运算符来做基本运算呢?

我会用这段代码除所有正数,非浮点数。基本上你要把除数位向左对齐以匹配被除数位。对于被除数的每一段(除数的大小),你想要检查是否被除数的每一段大于除数,然后你想要左Shift,然后在第一个注册器中OR。这个概念最初是在2004年创建的(我相信是斯坦福大学),这里是一个C版本,它使用了这个概念。注:(我做了一点修改)

int divide(int a, int b)
{
    int c = 0, r = 32, i = 32, p = a + 1;
    unsigned long int d = 0x80000000;

    while ((b & d) == 0)
    {
        d >>= 1;
        r--;
    }

    while (p > a)
    {
        c <<= 1;
        p = (b >> i--) & ((1 << r) - 1);
        if (p >= a)
            c |= 1;
    }
    return c; //p is remainder (for modulus)
}

使用示例:

int n = divide( 3, 6); //outputs 2
#include <stdio.h>

typedef struct { char a,b,c; } Triple;

unsigned long div3(Triple *v, char *r) {
  if ((long)v <= 2)  
    return (unsigned long)r;
  return div3(&v[-1], &r[1]);
}

int main() {
  unsigned long v = 21; 
  int r = div3((Triple*)v, 0); 
  printf("%ld / 3 = %d\n", v, r); 
  return 0;
}

用Pascal编写程序并使用DIV操作符。

因为问题被标记为c,你可以在Pascal中编写一个函数,然后在c程序中调用它;这样做的方法是特定于系统的。

但是这里有一个在我的Ubuntu系统上运行的例子,安装了Free Pascal fp-编译器包。(我这么做完全是出于不合时宜的固执;我不敢说这是有用的。)

divide_by_3。不是:

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.

c:

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

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