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

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


当前回答

用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

其他回答

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

首先是我想到的。

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。但是你可以使用字符串格式的想法,我猜…

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

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

如果你提醒自己标准的学校除法方法,用二进制来做,你会发现在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);
}

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

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