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

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

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

    这是执行所需操作的简单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

    贫乏的条件需要一个愚蠢的解决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

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

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

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

    (注意:请参阅下面的编辑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]); } 

    在Setun电脑上很容易。

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

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

    这是我的解决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 / 3div_by_3(a) 。 当a = 3k ,我们得到错误的答案。

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

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

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

    又一个解决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的差异应该是轻微的。

    这真的很容易。

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

    使用计数器是基本的解决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也很容易,请检查注释。

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

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

    例如,在Javacript中,你可以做

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

    用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 

    在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 

    首先,我已经想出了。

     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格式的想法,我猜…

    没有交叉检查这个答案是否已经发表。 如果程序需要扩展到浮点数,可以将数字乘以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; } 
     int div3(int x) { int reminder = abs(x); int result = 0; while(reminder >= 3) { result++; reminder--; reminder--; reminder--; } return result; } 

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

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

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

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

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

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

    看到我的另一个答案 。

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

    我认为正确的答案是:

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

    第一:

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