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

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


当前回答

(注意:查看下面的编辑2以获得更好的版本!)

这并不像听起来那么棘手,因为你说“没有使用[..+[…]运营商”。如果你想禁止同时使用+字符,请参见下面。

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    for (unsigned i = 0; i < by; i++)
      cmp++; // that's not the + operator!
    floor = r;
    r++; // neither is this.
  }
  return floor;
}

然后用div_by(100,3)将100除以3。


编辑:你可以继续并替换++操作符:

unsigned inc(unsigned x) {
  for (unsigned mask = 1; mask; mask <<= 1) {
    if (mask & x)
      x &= ~mask;
    else
      return x & mask;
  }
  return 0; // overflow (note that both x and mask are 0 here)
}

编辑2:稍快的版本,不使用任何包含+、-、*、/、%字符的操作符。

unsigned add(char const zero[], unsigned const x, unsigned const y) {
  // this exploits that &foo[bar] == foo+bar if foo is of type char*
  return (int)(uintptr_t)(&((&zero[x])[y]));
}

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    cmp = add(0,cmp,by);
    floor = r;
    r = add(0,r,1);
  }
  return floor;
}

我们使用add函数的第一个参数,因为不使用*字符就不能表示指针的类型,除非在函数形参列表中,其中的语法类型[]与类型* const相同。

FWIW,你可以很容易地实现一个乘法函数使用类似的技巧使用0x55555556技巧提出的AndreyT:

int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}

其他回答

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

使用黑客的喜悦魔术数字计算器

int divideByThree(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}

其中fma是在math.h头文件中定义的标准库函数。

这个方法(c#)怎么样?

private int dividedBy3(int n) {
        List<Object> a = new Object[n].ToList();
        List<Object> b = new List<object>();
        while (a.Count > 2) {
            a.RemoveRange(0, 3);
            b.Add(new Object());
        }
        return b.Count;
    }

首先是我想到的。

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

很有趣的是,没有人回答一个泛泛的划分:

/* For the given integer find the position of MSB */
int find_msb_loc(unsigned int n)
{
    if (n == 0)
        return 0;

    int loc = sizeof(n)  * 8 - 1;
    while (!(n & (1 << loc)))
        loc--;
    return loc;
}


/* Assume both a and b to be positive, return a/b */
int divide_bitwise(const unsigned int a, const unsigned int b)
{
    int int_size = sizeof(unsigned int) * 8;
    int b_msb_loc = find_msb_loc(b);

    int d = 0; // dividend
    int r = 0; // reminder
    int t_a = a;
    int t_a_msb_loc = find_msb_loc(t_a);
    int t_b = b << (t_a_msb_loc - b_msb_loc);

    int i;
    for(i = t_a_msb_loc; i >= b_msb_loc; i--)  {
        if (t_a > t_b) {
            d = (d << 1) | 0x1;
            t_a -= t_b; // Not a bitwise operatiion
            t_b = t_b >> 1;
         }
        else if (t_a == t_b) {
            d = (d << 1) | 0x1;
            t_a = 0;
        }
        else { // t_a < t_b
            d = d << 1;
            t_b = t_b >> 1;
        }
    }

    r = t_a;
    printf("==> %d %d\n", d, r);
    return d;
}

按位加法已经在其中一个答案中给出,所以跳过它。