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

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


当前回答

这应该适用于任何除数,而不仅仅是3。目前仅适用于unsigned,但将其扩展到signed应该没有那么困难。

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

其他回答

#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;
}
log(pow(exp(number),0.33333333333333333333)) /* :-) */

要将一个数除以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
}

我会用这段代码除所有正数,非浮点数。基本上你要把除数位向左对齐以匹配被除数位。对于被除数的每一段(除数的大小),你想要检查是否被除数的每一段大于除数,然后你想要左Shift,然后在第一个注册器中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

你可以考虑用图或树状结构来解决这个问题。基本上生成的顶点数与要除以3的数一样多。然后继续将每个未配对的顶点与其他两个顶点配对。

粗糙的伪代码:

function divide(int num)
    while(num!=0)
        Add a new vertice to vertiexList.
        num--
    quotient = 0
    for each in vertexList(lets call this vertex A)
        if vertexList not empty
            Add an edge between A and another vertex(say B)
        else
            your Remainder is 1 and Quotient is quotient
        if vertexList not empty
            Add an edge between A and another vertex(say C)
        else
            your remainder is 2 and Quotient is quotient
        quotient++
        remove A, B, C from vertexList
    Remainder is 0 and Quotient is quotient

这显然是可以优化的,复杂度取决于你的数字有多大,但它应该工作,只要你能做++和——。 这就像数更酷的东西一样。