如何将一个数除3而不使用*、/、+、-、%等运算符?

号码可以有签名,也可以没有签名。


当前回答

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

#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…

其他回答

这是一个执行所需操作的简单函数。但是它需要+操作符,所以你所要做的就是用位操作符来加值:

// 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 sum += an = a + b,然后迭代 当a == 0 (n < 4)时,sum += floor(n / 3);即1,如果n == 3,否则为0

这是经典的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);
}

似乎没有人提到用二进制表示的3的除法准则——偶数的和应该等于奇数的和(类似于十进制中11的准则)。在“检查一个数是否能被3整除”一栏中有使用这个技巧的解决方案。

我想这就是迈克尔·伯尔的编辑提到的可能的复制品。

哪里InputValue是数字除以3

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

用Pascal编写程序并使用DIV操作符。

因为问题被标记为c,你可以在Pascal中编写一个函数,然后在c程序中调用它;这样做的方法是特定于系统的。

但是这里有一个在我的Ubuntu系统上运行的例子,安装了Free Pascal fp-编译器包。(我这么做完全是出于不合时宜的固执;我不敢说这是有用的。)

divide_by_3。不是:

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.

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