不使用*、/、+、-、%运算符将一个数除以3

Question

不使用*、/、+、-、%运算符将一个数除以3

cmathbit-manipulationdivisiondivide

702

如何在不使用 *, /, +, -, % 运算符的情况下将一个数除以3？

这个数可以是有符号或无符号的。

- Green goblin

8

确认的重复项并不是重复的。请注意，这里有几个答案没有使用位移或加法，因为这个问题没有限制解决方案只能使用这些操作。 - Michael Burr

4

顺便说一下：另一个问题是关于检查数字是否能被3整除的。这个问题是关于除以3。 - wildplasser

4

x /= 3; 不使用 / 运算符，/= 是另一个运算符。 - James

28

这个问题不适合在SO上提问，它应该在http://codegolf.stackexchange.com/ 上发布。请注意，翻译尽量保持原义，同时让语言更通俗易懂，不包含任何解释或其他额外的信息。 - Kromster

3

我投票关闭此问题，因为它范围过于宽泛且不属于该领域，应该发布在 codegolf.stackexchange.com 上。目前的回答质量令人沮丧，这篇文章整体价值很小。 - Lundin

显示剩余9条评论

48个回答

441

愚蠢的情况需要一个愚蠢的解决方案：

#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,divisor)的结果添加到其上即可。 它的工作原理说明

fwrite函数写入number字节（例如上面的例子中是123456）。
rewind函数将文件指针重置为文件开头。
fread函数从文件中读取最多number/divisor个长度为divisor的记录，并返回它所读取的元素数量。

如果您写入了30个字节，并以3个字节为单位读回该文件，则会得到10个“单位”。 30/3 = 10。

- Matteo Italia

13

@earlNameless：你不知道他们在内部使用什么，它们处于“实现定义”的黑盒子中。没有任何东西阻止他们只使用位运算符；无论如何，它们都在我的代码域之外，所以这不是我的问题。 :) - Matteo Italia

8

@IvoFlipse从我清洁的东西中，你拿一个大物体，塞进一个小了三倍的东西里，然后看看可以塞多少。这差不多是三分之一。 - AncientSwordRage

29

我请公司最优秀的C程序员（也是最不擅长社交的）解释代码。他解释完后，我说这很巧妙。他说：“这个破玩意儿根本不是解决方案”，并让我离开他的桌子。 - user1107975

6

我认为重点在于这个问题太愚蠢了，以至于允许一个愚蠢的回答。你公司里的“最好的C程序员”也可以轻松地说：“那个垃圾不是一个（合适的）问题”。 - JeremyP

19

@JeremyP: 没错，我的意思是如果在现实生活中我得到了一个不支持算术运算的编译器，唯一明智的做法就是要求一个更好的编译器，因为在这种条件下工作没有任何意义。如果面试官想检查我如何使用位运算实现除法的知识，他可以直截了当地把它作为一个理论问题问出来；这种“恶作剧练习”只会引出这样的答案。 - Matteo Italia

显示剩余17条评论

310

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

- Alan Curry

2

如果四舍五入得当且数量不太大，这个可能实际可行。 - Mysticial

254

改进版：对数（底数为e）幂次方，指数为正弦值为atan2（1，sqrt（8））的数的自然指数。 - Alan Curry

@bitmask，数学函数通常直接在汇编中实现。 - SingerOfTheFall

8

我刚在我的JS控制台中输入了以下内容。但是，如果数值超过709，则无法正常工作（可能只是我的系统）。请参考以下两个示例：Math.log(Math.pow(Math.exp(709),0.33333333333333333333))和Math.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))。请注意，我已将其翻译为通俗易懂的中文，但未更改原意，并且没有提供任何解释或其他内容。 - Shaheer

209

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

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

- nos

113

你可以使用（与平台相关的）内联汇编，例如x86：（也适用于负数）

#include <stdio.h>

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

- moooeeeep

2

@JeremyP，您的评论是基于这种假设失败了，即答案不能用C语言编写？毕竟问题的标签是“C”。 - Seth Carnegie

1

@SethCarnegie 我的意思是答案不是用 C 语言写的。x86 汇编语言不是标准的一部分。 - JeremyP

1

@JeremyP 这是真的，但是 asm 指令是可行的。此外我要补充一点，C 编译器并不是唯一具有内嵌汇编器的编译器，Delphi 也有。 - Seth Carnegie

7

“asm”指令仅在C99标准的附录J-常见扩展中提到。 - JeremyP

2

在arm-eabi-gcc中失败。 - Damian Yerrick

显示剩余6条评论

107

使用itoa将其转换为基数为3的字符串。删除最后一个trit并将其转换回十进制。

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

- Bo Lu

4

如果你使用itoa实现一个完整的、能够正常工作的程序，并且该函数能够使用任意进制，那么我会点赞。我之前并不知道itoa可以使用任意进制。 - Mysticial

2

实现将包含 / 和 % ... :-) - R.. GitHub STOP HELPING ICE

2

@R.. 所以实现printf来显示您的十进制结果。 - Damian Yerrick

57

(注意：查看下面的修订版以获取更好的解决方案！)

这并不像听起来那么棘手，因为你说“不使用[..] + [..] 运算符”。如果您想完全禁止使用+字符，请参见下文。

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* const相同。

顺便提一句，您可以使用类似于AndreyT提出的0x55555556技巧来轻松实现乘法函数：

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

- bitmask

5

该问题的标签为[tag:c]，而不是SQL，尽管提到了Oracle。 - bitmask

3

确实，这看起来不像是SQL！ - moooeeeep

65

如果你能使用++，那为什么不直接使用/=呢？ - qwertz

5

++也是一个快捷方式，等同于num = num + 1。 - qwertz

4

是的，但+=最终是num = num + 1的快捷方式。 - qwertz

显示剩余7条评论

43

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

要将整数除以3，向右移1位。

我不确定在这样的平台上是否严格可能实现符合规范的C编译器。我们可能需要放宽规则，比如将“至少8位”解释为“能够容纳至少从-128到+127的整数”。

- Mechanical snail

8

问题在于C语言中没有“向右移动1位”的运算符。>>运算符是“除以2的n次方”的运算符，即它是根据算术而非机器表示来指定的。 - R.. GitHub STOP HELPING ICE

Setun计算机在任何意义上都不是二进制的，因此指令集必须明显不同。然而，我对该计算机的操作一窍不通，因此无法确认响应是否真正正确 - 但至少它是有意义的，并且非常独特。+1 - virolino

34

这是我的解决方案：

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

- tschultz

2

对于输入值为3，这个程序可以正常工作吗？1/4, 1/16, ...等所有值在3的情况下都是0，因此它们的总和为0，但是3/3 = 1。 - hatchet - done with SOverflow

1

逻辑不错，但实现有问题。n/3的级数逼近始终小于n/3，这意味着对于任何n=3k，结果将是k-1而不是k。 - Xyand

@Albert，这是我尝试的第一种方法，有几个变化版本，但它们都无法处理某些可以被3整除或2整除（取决于变化）的数字。因此，我尝试了一些更简单明了的方法。我想看到一个可以正常工作的该方法实现，以便了解我哪里出错了。 - hatchet - done with SOverflow

@hatchet，问题已关闭，所以我无法发布新答案，但是想法是实现二进制除法。应该很容易查找。 - Xyand

黑客的乐趣有一些舍入方法可以获得正确的结果。 (http://www.hackersdelight.org/divcMore.pdf) - phuclv

25

将一个32位的数字除以3，可以先将其乘以0x55555556，然后取64位结果的高32位。

现在只需使用位运算和移位操作来实现乘法即可...

- AnT stands with Russia

1

这是一个常见的编译器技巧，用于解决缓慢除法问题。但你可能需要进行一些修正，因为0x55555556 / 2 ** 32并不完全等于1/3。 - CodesInChaos

“multiply it”。这不意味着使用被禁止的 * 运算符吗？ - luiscubal

8

不会。这就是我说：“现在只剩下使用位运算和移位实现乘法”原因。 - AnT stands with Russia

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- qwertz · Accepted Answer

这是一个简单函数，用于执行所需操作。但它需要使用+运算符，因此您只需要使用位运算符添加值即可：

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

正如Jim所评论的那样，这个程序是有效的，因为：

n = 4 * a + b
n / 3 = a + (a + b) / 3
所以sum += a，n = a + b，并循环迭代
当a == 0 (n < 4)时，sum += floor(n / 3); 即1，if n == 3, else 0

不使用*、/、+、-、%运算符将一个数除以3

编辑：您还可以替换++运算符：

编辑 2：在不使用包含 +,-,*,/,% 这些 字符 的任何运算符的情况下略微更快的版本。

编辑：您还可以替换`++`运算符：

编辑 2：在不使用包含 `+`,`-`,`*`,`/`,`%` 这些字符的任何运算符的情况下略微更快的版本。