logo标签列表

不使用*、/、+、-、%运算符将一个数除以3

cmathbit-manipulationdivisiondivide
702

如何在不使用 *, /, +, -, % 运算符的情况下将一个数除以3？

这个数可以是有符号或无符号的。

8
确认的重复项并不是重复的。请注意，这里有几个答案没有使用位移或加法，因为这个问题没有限制解决方案只能使用这些操作。 - Michael Burr
4
顺便说一下：另一个问题是关于检查数字是否能被3整除的。这个问题是关于除以3。 - wildplasser
4
x /= 3; 不使用 / 运算符，/= 是另一个运算符。 - James
28
这个问题不适合在SO上提问，它应该在http://codegolf.stackexchange.com/ 上发布。请注意，翻译尽量保持原义，同时让语言更通俗易懂，不包含任何解释或其他额外的信息。 - Kromster
3
我投票关闭此问题，因为它范围过于宽泛且不属于该领域，应该发布在 codegolf.stackexchange.com 上。目前的回答质量令人沮丧，这篇文章整体价值很小。 - Lundin
显示剩余9条评论
48个回答
2

好的，我想我们都认为这不是一个真实世界的问题。所以，仅仅为了好玩，下面是如何使用Ada和多线程来解决它：

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;
这是标记为C语言的，从一开始就是这样。你的回答与主题无关。 - Lundin
挖掘旧的、关闭的问题并在答案上写这种评论也是如此。这对我们双方来说都是浪费时间，因为你必须写评论，而我则需要看到通知，点击它并需要理解上下文。这既不会教育我（我甚至记不起自己写过这个问题），也不会改善答案（你真的认为我会将其翻译成C语言吗）。你想要达到什么目的？ - flyx
问题在于该问题并未关闭，因此产生了大量的离题、低质量的垃圾答案，并且仍在不断涌现。我正在尝试通过检查答案、标记非答案和对离题答案进行投票来提高网站的质量。顺便说一下，这是社区维基，因此不会影响声望。 - Lundin
好的，我改正。关闭问题以阻止新答案不是更容易吗？ - flyx
你拥有我的剑。 - flyx
2
所有的答案可能都不是面试官想要听到的：
我的回答：
“我永远不会这样做，谁会为这种愚蠢的事情付钱。没有人会因此获得优势，这不是更快，只是愚蠢。处理器设计师必须知道这一点，但这必须适用于所有数字，而不仅仅是除以3。”
什么让你觉得面试官不想听这个？在我的面试中，任何一个给出这样回答的候选人都会增加他们获得工作的机会。在一片混乱中，有一个理智的人... - Lundin
1
如果你回忆起标准学校的除法方法，然后用二进制方式进行计算，你会发现在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);
}
1
#include <stdio.h>

typedef struct { char a,b,c; } Triple;

unsigned long div3(Triple *v, char *r) {
  if ((long)v <= 2)  
    return (unsigned long)r;
  return div3(&v[-1], &r[1]);
}

int main() {
  unsigned long v = 21; 
  int r = div3((Triple*)v, 0); 
  printf("%ld / 3 = %d\n", v, r); 
  return 0;
}
1
为什么不直接应用在大学学习的定义呢？结果可能效率低下，但很清晰，因为乘法只是递归减法，减法是加法，那么加法可以通过递归异或/与逻辑端口组合来执行。
#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...

0

在Assembly编程语言中，为了将一个数除以3而不使用乘法、除法、取余、减法或加法操作，唯一可用的指令是LEA（有效地址装入）、SHL（向左移动）和SHR（向右移动）。

通过这种解决方案，我没有使用与运算符+ - * /%相关的操作。

我假设输出数字采用定点格式（16位整数部分和16位小数部分），输入数字为short int类型；但是，由于只能信任整数部分，因此我近似了输出数量，因此返回short int类型的值。

65536/6是等效于1/3浮点数的定点值，等于21845。

21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1。

因此，要进行乘以1/3（21845）的操作，我使用LEA和SHL指令。

short int DivideBy3( short int num )
//In : eax= 16 Bit short int input number (N)
//Out: eax= N/3 (32 Bit fixed point output number
//          (Bit31-Bit16: integer part, Bit15-Bit0: digits after comma)
{
   __asm
   {
      movsx eax, num          // Get first argument

      // 65536 / 3 = 21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1

      lea edx,[4*eax+eax]     // EDX= EAX * 5
      shl eax,4
      lea edx,[eax+edx]       // EDX= EDX + EAX * 16
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 64
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 256
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 1024
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 4096
      shl eax,2
      lea edx,[eax+edx+08000h] // EDX= EDX + EAX * 16384

      shr edx,010h
      movsx eax,dx

   }
   // Return with result in EAX
}

它也适用于负数；结果与正数有最小的近似值（在逗号后的最后一位为-1）。

如果您不打算使用+ - * /%运算符执行除以3的操作，但可以使用与它们相关联的操作，则我提出第二个解决方案。

int DivideBy3Bis( short int num )
//In : eax= 16 Bit short int input number (N)
//Out: eax= N/3 (32 Bit fixed point output number
//          (Bit31-Bit16: integer part, Bit15-Bit0: digits after comma)
{
   __asm
   {
      movsx   eax, num        // Get first argument

      mov     edx,21845
      imul    edx
   }
   // Return with result in EAX
}
0
#!/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
OP要求使用C语言而不是Ruby的解决方案。 - c.hill
问题中没有提及C语言，只是标签而已。很抱歉，你未被雇佣;) - A B
1
我非常确定你可以使用popen()将Ruby调用包装为C的外部调用。 - A B
0

如果我们认为__div__不是用斜杠/来表示的话

def divBy3(n):
    return n.__div__(3)

print divBy3(9), 'or', 9//3
0

2进制中的3是11。

因此，只需在基数为2的情况下进行长除法（就像在中学时一样）。 在基数为2的情况下比在基数为10的情况下更容易。

从最高有效位开始的每个二进制位位置：

确定前缀是否小于11。

如果输出0。

如果不是输出1，然后替换相应的前缀位。 只有三种情况：

 11xxx ->    xxx    (ie 3 - 3 = 0)
100xxx ->   1xxx    (ie 4 - 3 = 1)
101xxx ->  10xxx    (ie 5 - 3 = 2)

所有其他前缀都是无法到达的。

重复直到最低位位置，然后完成。

0
我会使用这段代码来除以所有正数、非浮点数。基本上，您想将除数位对齐到左侧以匹配被除数位。对于每个被除数的片段（大小为除数），您要检查是否该被除数的片段大于除数，然后您要向左移动并在第一个寄存器中进行OR运算。这个概念最初是在2004年创建的（我相信是斯坦福大学），这里是一个使用该概念的C版本。注意：（我稍微修改了一下）
int divide(int a, int b)
{
    int c = 0, r = 32, i = 32, p = a + 1;
    unsigned long int d = 0x80000000;

    while ((b & d) == 0)
    {
        d >>= 1;
        r--;
    }

    while (p > a)
    {
        c <<= 1;
        p = (b >> i--) & ((1 << r) - 1);
        if (p >= a)
            c |= 1;
    }
    return c; //p is remainder (for modulus)
}

示例用法：

int n = divide( 3, 6); //outputs 2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接