将数字除以3，不使用*，/，+， – ，％运算符

你如何将数字除以3而不用* ， / ， + ， - ， % ，操作符？

该号码可以是有符号的或无符号的。

Answer 1

这是执行所需操作的简单function 。 但是它需要+操作符，所以你所要做的就是用位操作符来添加值：

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

Answer 2

贫乏的条件需要一个愚蠢的解决scheme：

 #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)的结果中。

它是如何工作的解释

1. fwrite写入number字节（在上面的例子中，数字是123456）。
2. rewind将文件指针重置为文件的前面。
3. fread从文件中读取最大长度为divisor “logging” divisor ，并返回读取的元素数。

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

使用itoa转换为基本3string。 放下最后一块，并转换回基地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 } 

Answer 7

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

---

编辑 ：您可以继续并replace++运算符：

 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相同的情况下，我们不能指示不使用*字符的指针type* const 。

FWIW，你可以很容易的使用类似的技巧来实现一个乘法函数来使用0x55555556提出的0x55555556技巧：

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

Answer 8

在Setun电脑上很容易。

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

我不确定是否可以在这样的平台上实现一致的C编译器。 我们可能需要稍微扩展一些规则，比如将“至less8位”解释为“能够保持从-128到+127的整数”。

Answer 9

这是我的解决scheme：

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

现在我们所要做的就是把这些位移值加起来！ 哎呀！ 我们不能添加，所以我们必须使用按位运算符来编写一个添加函数！ 如果你熟悉按位运算符，我的解决scheme应该看起来相当简单…但是如果你不熟悉，我会在最后通过一个例子。

另外要注意的是，首先我向左移动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的div_by_3(a) 。 当a = 3k ，我们得到错误的答案。

Answer 10

既然是来自甲骨文，那么预先计算答案的查询表呢？ 😀

Answer 11

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

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

Answer 12

又一个解决scheme。 除了int的最小值之外，它应该处理所有的整数（包括负整数），这需要作为硬编码的exception来处理。 这基本上是通过减法除法，但只使用位操作符（移位，异或，和补码）。 为了更快的速度，它减去3 *（降低2的幂）。 在c＃中，它每毫秒执行这些DivideBy3调用的大约444次（对于1,000,000个分频为2.2秒），所以不会非常慢，但不会像简单的x / 3一样快。 相比之下，Coodey的解决scheme比这个快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的差异应该是轻微的。

Answer 13

这真的很容易。

 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; 

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

Answer 14

使用计数器是基本的解决scheme：

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

执行模数function也很容易，请检查注释。

Answer 15

这是基础2中的经典除法algorithm：

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

Answer 16

通过使用eval和string连接来使用“幕后”的/运算符会是作弊吗？

例如，在Javacript中，你可以做

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

Answer 17

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

由于问题标记为c ，因此可以在Pascal中编写函数并从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 <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; } 

build立：

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

样例执行：

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

Answer 18

在PHP中使用BCmath ：

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

Answer 19

首先，我已经想出了。

 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 但是，你可以使用关于string格式的想法，我猜…

Answer 20

没有交叉检查这个答案是否已经发表。 如果程序需要扩展到浮点数，可以将数字乘以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; } 

Answer 21

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

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

Answer 22

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

Answer 23

以下脚本生成一个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)); } ''') 

Answer 24

使用黑客的喜悦魔术数字计算器

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

其中fma是math.h头文件中定义的标准库函数。

Answer 25

这个方法怎么样（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; } 

Answer 26

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

看到我的另一个答案 。

Answer 27

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

Answer 28

我认为正确的答案是：

为什么我不会用一个基本的操作员来做一个基本的操作？

Answer 29

第一：

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

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

Answer 30

好吧，我认为我们都同意这不是一个真正的世界问题。 所以只是为了好玩，下面是如何使用Ada和multithreading来做到这一点：

 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;