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

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


当前回答

int div3(int x)
{
  int reminder = abs(x);
  int result = 0;
  while(reminder >= 3)
  {
     result++;

     reminder--;
     reminder--;
     reminder--;
  }
  return result;
}

其他回答

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

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

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

要将一个数除以3,而不使用乘法、除法、余数、减法或加法操作,在汇编编程语言中,惟一可用的指令是LEA(地址有效负载)、SHL(向左移动)和SHR(向右移动)。

在这个解决方案中,我没有使用与运算符+ - * /%相关的操作

我假设有输出数字在定点格式(16位整数部分和16位小数部分)和输入数字的类型是短int;但是,我已经近似输出的数量,因为我只能信任整数部分,因此我返回一个短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
}

并不是所有的答案都是面试官想听到的:

我的回答:

“我绝不会那样做,谁会为这种愚蠢的事情付出代价呢?”没有人 会有一个优势,它不是更快,它只是愚蠢。 教授设计师必须知道这一点,但这必须适用于所有数字,而不仅仅是除以3。”

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

请看我的另一个答案。