首页 文章

将数字除以3而不使用除法，乘法或模数

提问于
浏览 次
0

不使用/，％和*运算符，编写一个函数将数字除以3. itoa（）可用 .

以上是我在接受采访时问到的，我无法真正得出答案 . 我想将数字转换为字符串并添加所有数字，但这只会告诉我数字是否可以整除 . 或者，通过重复减法，它也可以告诉我剩余部分 . 但是，我如何获得除法的商？

algorithm

3 回答

  • 1

    下面的代码接受2个整数，并将第一个除以第二个 . 它支持负数 .

    int divide (int a, int b) {
    if (b == 0)
        //throw division by zero error

    //isPos is used to check whether the answer is positive or negative
    int isPos = 1;
    //if the signs are different, the answer will be negative
    if ((a < 0 && b > 0) || (a > 0 && b < 0))
        int isPos = 0;


    a = Math.abs(a);
    b = Math.abs(b);
    int ans = 0;
    while (a >= b) {
        a = a-b;
        ans++;
    }
    if (isPos)
        return 0-ans;
    return ans;
}
    回复于
  • 0

    根据itoa，数字是整数 .

    int divide(int a, int b)
{
  int n=0;
  while(1)
  {
    a-=b;
    if(a<b)
    {
      n=n+1;
      return n;
    }
    else
     n=n+1;
  }
}

    只需计算减去b的次数即可

    编辑：删除限制

    回复于
  • 1

    “计算减去3次的算法”算法采用theta（| input |）步骤 . 您可能会认为theta（| input |）适用于32位整数，在这种情况下为什么要进行任何编程？只需使用查找表 . 但是，有更快的方法可用于更大的输入 .

    您可以对商进行二元搜索，通过将q q q与输入进行比较来测试候选商q是否太大或太小 . 二进制搜索需要theta（log | input |）时间 .

    二进制搜索使用除以2，这可以由移位运算符而不是/来完成，或者如果移位运算符太接近除法，您可以在位数组上自己实现 .

    通过尝试（n >> 2）（n >> 4），使用1/3是几何级数1/4 1/16 1/64 1/256之和的事实是很诱人的（n> > 6）......然而，对于n = 3,6,7,9,11,12,13,14,15,18，......这产生了错误的答案......对于n = 15,30，它关闭了两个， 31,39，....一般来说，这是由O（log n）关闭的 . 对于n非负，

    (n>>2) + (n>>4) + (n>>6) + ...  = (n-wt4(n))/3

    其中wt4（n）是n的基数4位的和，右侧的/是精确的，而不是整数除法 . 我们可以通过将wt4（n）/ 3加到（n >> 2）（n >> 4）（n >> 6）来计算n / 3.我们可以计算n的基数4，因此wt4（n） ）仅使用加法和右移 .

    int oneThirdOf(int n){
    if (0<=n && n<3)
        return 0;
    if (n==3)
        return 1;
    return sum(n) + oneThirdOf(wt4(n));
}

// Compute (n>>2) + (n>>4) + (n>>6) + ... recursively.
int sum(int n){
    if (n<4)
        return 0;
    return (n>>2) + sum(n>>2);
}

// Compute the sum of the digits of n base 4 recursively.
int wt4(int n){
    if (n<4)
        return n;
    int fourth = n>>2;
    int lastDigit = n-fourth-fourth-fourth-fourth;
    return wt4(fourth) + lastDigit;
}

    这也需要theta（日志输入）步骤 .

    回复于

相关问题