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

由于问题被标记为 c，因此您可以在 Pascal 中编写一个函数并从您的 C 程序中调用它;执行此操作的方法是特定于系统的。

但这里有一个示例，适用于安装了 Free Pascal 软件包的 Ubuntu 系统。（我这样做纯粹是出于错位的固执;我不声称这是有用的。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 <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

（注意：请参阅下面的编辑 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)1003

---

编辑：您也可以继续并替换操作员：++

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

FWIW，您可以使用类似的技巧轻松实现乘法函数，以使用 AndreyT 提出的技巧：0x55555556

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

使用 itoa 转换为以 3 为基数的字符串。删除最后一个 trit 并转换回基数 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
}

这是一个执行所需操作的简单函数。但它需要运算符，所以你剩下要做的就是用位运算符添加值：+

// 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 += an = a + b

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

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

现在剩下要做的就是使用位运算和移位实现乘法......

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

愚蠢的条件需要一个愚蠢的解决方案：

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

如果还需要小数部分，只需声明为 并将 的结果添加到其中。resultdoublefmod(number,divisor)

工作原理说明

1. 写入字节数（在上面的示例中123456数字）。fwritenumber
2. rewind将文件指针重置为文件前面。
3. fread从文件中读取最大长度的“记录”，并返回它读取的元素数。numberdivisor

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

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

您可以使用（取决于平台的）内联汇编，例如，对于 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;
}

使用 Hacker's Delight Magic 数字计算器

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

其中 fma 是在 header 中定义的标准库函数。math.h

这是我的解决方案：

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

假设 = x 的 reslut，则 .当 ， 我们得到错误的答案。div_by_3(a)x <= floor(f(a, i)) < a / 3a = 3k

又一个解决方案。这应该处理除 int 的最小值之外的所有 int（包括负 int），这需要作为硬编码异常进行处理。这基本上是通过减法进行除法，但只使用位运算符（shifts、xor、& 和 complement）。为了获得更快的速度，它减去 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 的区别应该很小。

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

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

不过，我不确定在这样的平台上是否严格可能实现符合要求的 C 编译器。我们可能不得不稍微扩展规则，例如将“至少 8 位”解释为“能够保存至少从 -128 到 +127 的整数”。

首先，我想出了。

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

这是以 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);
}

使用 cblas，它包含在 OS X 的 Accelerate 框架中。

[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>

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

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

#include <stdio.h>

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

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

#include <stdio.h>

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

#!/bin/ruby

def div_by_3(i)
  i.div 3        # always return int http://www.ruby-doc.org/core-1.9.3/Numeric.html#method-i-div
end

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

看看我的另一个答案。

这里是 Python 语言，基本上是字符串比较和状态机。

def divide_by_3(input):
  to_do = {}
  enque_index = 0
  zero_to_9 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  leave_over = 0
  for left_over in (0, 1, 2):
    for digit in zero_to_9:
      # left_over, digit => enque, leave_over
      to_do[(left_over, digit)] = (zero_to_9[enque_index], leave_over)
      if leave_over == 0:
        leave_over = 1
      elif leave_over == 1:
        leave_over = 2
      elif leave_over == 2 and enque_index != 9:
        leave_over = 0
        enque_index = (1, 2, 3, 4, 5, 6, 7, 8, 9)[enque_index]
  answer_q = []
  left_over = 0
  digits = list(str(input))
  if digits[0] == "-":
    answer_q.append("-")
  digits = digits[1:]
  for digit in digits:
    enque, left_over = to_do[(left_over, int(digit))]
    if enque or len(answer_q):
      answer_q.append(enque)
  answer = 0
  if len(answer_q):
    answer = int("".join([str(a) for a in answer_q]))
  return answer

在 PHP 中使用 BC Math：

<?php
    $a = 12345;
    $b = bcdiv($a, 3);   
?>

---

MySQL（这是来自Oracle的采访）

> SELECT 12345 DIV 3;

---

帕斯卡：

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

---

x86-64 汇编语言：

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

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

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

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

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

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

使用 Linux shell 脚本：

#include <stdio.h>
int main()
{
    int number = 30;
    char command[25];
    snprintf(command, 25, "echo $((%d %c 3)) ", number, 47);
    system( command );
    return 0;
}

看看我的另一个答案。

以下脚本生成一个 C 程序，该程序在不使用运算符的情况下解决问题：* / + - %

#!/usr/bin/env python3

print('''#include <stdint.h>
#include <stdio.h>
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));
}
''')

这真的很容易。

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;

（当然，为了简洁起见，我省略了一些程序。如果程序员厌倦了把这些都输入出来，我相信他或她可以写一个单独的程序来为他生成它。我碰巧知道某个操作员，这将极大地简化他的工作。/

通过使用字符串连接在“幕后”使用运算符会作弊吗？/eval

例如，在 Javacript 中，您可以执行以下操作

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

好 'ol bc：

$ num=1337; printf "scale=5;${num}\x2F3;\n" | bc
445.66666

如果我们考虑不是正交的__div__/

def divBy3(n):
    return n.__div__(3)

print divBy3(9), 'or', 9//3

以 3 为基数的 2 是 11。

因此，只需在基数 2 乘以 11 的情况下进行长除法（如在中学）。以 2 为基数比以 10 为基数更容易。

对于每个位位置，从最高有效开始：

确定前缀是否小于 11。

如果输出为 0.

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

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

所有其他前缀都无法访问。

重复直到最低位位置，您就完成了。

这是我爷爷在我小时候教给我的一种方法。它需要 + 和 / 运算符，但它使计算变得容易。

将各个数字相加，然后查看它是否是 3 的倍数。

但这种方法适用于大于 12 的数字。

示例：36，

3+6=9，是 3 的倍数。

42,

4+2=6，是 3 的倍数。

好吧，你可以考虑使用类似图/树的结构来解决这个问题。基本上生成与要除以 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

这显然是可以优化的，复杂性取决于你的数字有多大，但只要你可以做++和--.，它就应该起作用 这就像只计算更酷一样好。

这种方法 （c#） 怎么样？

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

我认为正确的答案是：

为什么我不使用基本运算符来执行基本操作？

第一：

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

虽然它使用 ，但有人已经实现了按位运算的加法。+

好吧，我想我们都同意这不是一个现实世界的问题。因此，为了好玩，以下是使用 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;

很有趣，没有人用通用的划分来回答：

/* For the given integer find the position of MSB */
int find_msb_loc(unsigned int n)
{
    if (n == 0)
        return 0;

    int loc = sizeof(n)  * 8 - 1;
    while (!(n & (1 << loc)))
        loc--;
    return loc;
}


/* Assume both a and b to be positive, return a/b */
int divide_bitwise(const unsigned int a, const unsigned int b)
{
    int int_size = sizeof(unsigned int) * 8;
    int b_msb_loc = find_msb_loc(b);

    int d = 0; // dividend
    int r = 0; // reminder
    int t_a = a;
    int t_a_msb_loc = find_msb_loc(t_a);
    int t_b = b << (t_a_msb_loc - b_msb_loc);

    int i;
    for(i = t_a_msb_loc; i >= b_msb_loc; i--)  {
        if (t_a > t_b) {
            d = (d << 1) | 0x1;
            t_a -= t_b; // Not a bitwise operatiion
            t_b = t_b >> 1;
         }
        else if (t_a == t_b) {
            d = (d << 1) | 0x1;
            t_a = 0;
        }
        else { // t_a < t_b
            d = d << 1;
            t_b = t_b >> 1;
        }
    }

    r = t_a;
    printf("==> %d %d\n", d, r);
    return d;
}

在其中一个答案中已经给出了按位加法，因此请跳过它。

所有的答案可能不是面试官喜欢听到的：

我的回答：

“我永远不会那样做，我为这种愚蠢的事情付出了代价。没有人 在这方面会有一个优势，它不是更快，它只是愚蠢的。 Prozessor 设计师必须知道这一点，但这必须适用于所有数字，而不仅仅是除以 3”

似乎没有人提到以二进制表示的 3 的除法标准——偶数的总和应等于奇数的总和（类似于十进制的 11 标准）。在检查数字是否能被 3 整除下，有使用此技巧的解决方案。

我想这是迈克尔·伯尔（Michael Burr）的编辑提到的可能的重复。

数字除以 3 在哪里InputValue

SELECT AVG(NUM) 
  FROM (SELECT InputValue NUM from sys.dual
         UNION ALL SELECT 0 from sys.dual
         UNION ALL SELECT 0 from sys.dual) divby3

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

我们为什么不直接应用大学里学的定义呢？结果可能效率低下，但很清楚，因为乘法只是递归减法，而减法是加法，那么加法可以通过递归异或/和逻辑端口组合来执行。

#include <stdio.h>

int add(int a, int b){
   int rc;
   int carry;
   rc = a ^ b; 
   carry = (a & b) << 1;
   if (rc & carry) 
      return add(rc, carry);
   else
      return rc ^ carry; 
}

int sub(int a, int b){
   return add(a, add(~b, 1)); 
}

int div( int D, int Q )
{
/* lets do only positive and then
 * add the sign at the end
 * inversion needs to be performed only for +Q/-D or -Q/+D
 */
   int result=0;
   int sign=0;
   if( D < 0 ) {
      D=sub(0,D);
      if( Q<0 )
         Q=sub(0,Q);
      else
         sign=1;
   } else {
      if( Q<0 ) {
         Q=sub(0,Q);
         sign=1;
      } 
   }
   while(D>=Q) {
      D = sub( D, Q );
      result++;
   }
/*
* Apply sign
*/
   if( sign )
      result = sub(0,result);
   return result;
}

int main( int argc, char ** argv ) 
{
    printf( "2 plus 3=%d\n", add(2,3) );
    printf( "22 div 3=%d\n", div(22,3) );
    printf( "-22 div 3=%d\n", div(-22,3) );
    printf( "-22 div -3=%d\n", div(-22,-3) );
    printf( "22 div 03=%d\n", div(22,-3) );
    return 0;
}

正如有人所说......首先，完成这项工作。请注意，算法应适用于负 Q...

通常，解决此问题的方法是：

log(pow(exp(numerator),pow(denominator,-1)))

我将使用此代码除以所有正的非浮点数。基本上，您希望将除数位向左对齐以匹配被除数位。对于要检查的除数的每个段（除数的大小），以确保被除数段是否大于除数，则要在第一个注册器中向左移动，然后向 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

这将起作用：

smegma$ curl http://www.wolframalpha.com/input/?i=14+divided+by+3 2>/dev/null | gawk 'match($0, /link to /input/\?i=([0-9.+-]+)/, ary) { print substr( $0, ary[1, "start"], ary[1, "length"] )}' 4.6666666666666666666666666666666666666666666666666666

只需用您的数字替换“14”和“3”即可。

如果你提醒自己标准的学校除法方法，并以二进制形式进行，你会发现，在3的情况下，你只除减一组有限的值（在这种情况下从0到5）。这些可以用 switch 语句来处理，以摆脱算术运算符。

static unsigned lamediv3(unsigned n)
{
  unsigned result = 0, remainder = 0, mask = 0x80000000;

  // Go through all bits of n from MSB to LSB.
  for (int i = 0; i < 32; i++, mask >>= 1)
  {
    result <<= 1;
    // Shift in the next bit of n into remainder.
    remainder = remainder << 1 | !!(n & mask);

    // Divide remainder by 3, update result and remainer.
    // If remainder is less than 3, it remains intact.
    switch (remainder)
    {
    case 3:
      result |= 1;
      remainder = 0;
      break;

    case 4:
      result |= 1;
      remainder = 1;
      break;

    case 5:
      result |= 1;
      remainder = 2;
      break;
    }
  }

  return result;
}

#include <cstdio>

int main()
{
  // Verify for all possible values of a 32-bit unsigned integer.
  unsigned i = 0;

  do
  {
    unsigned d = lamediv3(i);

    if (i / 3 != d)
    {
      printf("failed for %u: %u != %u\n", i, d, i / 3);
      return 1;
    }
  }
  while (++i != 0);
}

要在不使用乘法、除法、余数、减法或加法运算的情况下将数字除以 3，在汇编编程语言中，唯一可用的指令是 LEA（地址有效负载）、SHL（向左移动）和 SHR（向右移动）。

使用此解决方案，我没有使用与运算符 + - * /% 关联的操作

我假设输出数字为定点格式（16 位整数部分和 16 位小数部分），输入数字为 short int 类型;但是，我已经估算了输出的数量，因为我只能信任整数部分，因此我返回了一个 short int 类型的值。

65536/6 是相当于 1/3 浮点的定点值，等于 21845。

21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1。

因此，为了进行 1/3 （21845） 的乘法运算，我使用指令 LEA 和 SHL。

short int DivideBy3( short int num )
//In : eax= 16 Bit short int input number (N)
//Out: eax= N/3 (32 Bit fixed point output number
//          (Bit31-Bit16: integer part, Bit15-Bit0: digits after comma)
{
   __asm
   {
      movsx eax, num          // Get first argument

      // 65536 / 3 = 21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1

      lea edx,[4*eax+eax]     // EDX= EAX * 5
      shl eax,4
      lea edx,[eax+edx]       // EDX= EDX + EAX * 16
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 64
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 256
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 1024
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 4096
      shl eax,2
      lea edx,[eax+edx+08000h] // EDX= EDX + EAX * 16384

      shr edx,010h
      movsx eax,dx

   }
   // Return with result in EAX
}

它也适用于负数;结果具有正数的最小近似值（逗号后最后一位数字为 -1）。

如果您不打算使用运算符 + - * /% 来执行除以 3，但您可以使用与它们相关的运算，我建议第二种解决方案。

int DivideBy3Bis( short int num )
//In : eax= 16 Bit short int input number (N)
//Out: eax= N/3 (32 Bit fixed point output number
//          (Bit31-Bit16: integer part, Bit15-Bit0: digits after comma)
{
   __asm
   {
      movsx   eax, num        // Get first argument

      mov     edx,21845
      imul    edx
   }
   // Return with result in EAX
}