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

### 30 Solutions collect form web for “将数字除以3，不使用*，/，+， – ，％运算符”

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

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

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

` `log(pow(exp(number),0.33333333333333333333)) /* :-) */` `
` `#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; }` `

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

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

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

### 编辑 ：您可以继续并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; }` `

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

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

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

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

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

` `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这些，我相信他或她可以编写一个单独的程序来为他生成它。 我碰巧知道某个操作员会极大地简化他的工作。

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

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

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

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

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

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

` `#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; }` `
` `int div3(int x) { int reminder = abs(x); int result = 0; while(reminder >= 3) { result++; reminder--; reminder--; reminder--; } return result; }` `

` `#!/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)); } ''')` `

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

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

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

` `[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` `

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

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

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

` `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;` `
• 计算两点之间的距离（经度，纬度）
• 如何获得一个数字的整数和小数部分？
• 以百分比forms编号
• 计算LookAtmatrix
• 通用C＃代码和Plus运算符
• 什么是计算机科学的NP完整？
• “mod”和“remaining”之间有什么区别？
• 正数在JavaScript中的负数？
• Ruby：将负数改为正数？
• 最快的方式列出N以下的所有素数
• 我怎么能检查一个数字是一个完美的广场？