如何将一个数除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]);
}

其他回答

这是经典的2进制除法算法

#include <stdio.h>
#include <stdint.h>

int main()
{
  uint32_t mod3[6] = { 0,1,2,0,1,2 };
  uint32_t x = 1234567; // number to divide, and remainder at the end
  uint32_t y = 0; // result
  int bit = 31; // current bit
  printf("X=%u   X/3=%u\n",x,x/3); // the '/3' is for testing

  while (bit>0)
  {
    printf("BIT=%d  X=%u  Y=%u\n",bit,x,y);
    // decrement bit
    int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
    uint32_t r = x>>bit;  // current remainder in 0..5
    x ^= r<<bit;          // remove R bits from X
    if (r >= 3) y |= 1<<bit; // new output bit
    x |= mod3[r]<<bit;    // new remainder inserted in X
  }
  printf("Y=%u\n",y);
}

Yet another solution. This should handle all ints (including negative ints) except the min value of an int, which would need to be handled as a hard coded exception. This basically does division by subtraction but only using bit operators (shifts, xor, & and complement). For faster speed, it subtracts 3 * (decreasing powers of 2). In c#, it executes around 444 of these DivideBy3 calls per millisecond (2.2 seconds for 1,000,000 divides), so not horrendously slow, but no where near as fast as a simple x/3. By comparison, Coodey's nice solution is about 5 times faster than this one.

public static int DivideBy3(int a) {
    bool negative = a < 0;
    if (negative) a = Negate(a);
    int result;
    int sub = 3 << 29;
    int threes = 1 << 29;
    result = 0;
    while (threes > 0) {
        if (a >= sub) {
            a = Add(a, Negate(sub));
            result = Add(result, threes);
        }
        sub >>= 1;
        threes >>= 1;
    }
    if (negative) result = Negate(result);
    return result;
}
public static int Negate(int a) {
    return Add(~a, 1);
}
public static int Add(int a, int b) {
    int x = 0;
    x = a ^ b;
    while ((a & b) != 0) {
        b = (a & b) << 1;
        a = x;
        x = a ^ b;
    }
    return x;
}

这是c#,因为这是我手边的东西,但与c的区别应该很小。

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

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

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

如果我们认为__div__不是正字法上的/

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

print divBy3(9), 'or', 9//3
#!/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