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

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


当前回答

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

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

其他回答

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的区别应该很小。

在PHP中使用BC数学:

<?php
    $a = 12345;
    $b = bcdiv($a, 3);   
?>

MySQL(来自Oracle的采访)

> SELECT 12345 DIV 3;

帕斯卡:

a:= 12345;
b:= a div 3;

X86-64汇编语言:

mov  r8, 3
xor  rdx, rdx   
mov  rax, 12345
idiv r8

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

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

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

使用itoa转换为以3为基数的字符串。去掉最后一个小调,转换回10进制。

// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
    char str[42];
    sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
    if (i>0)                     // Remove sign if positive
        str[0] = ' ';
    itoa(abs(i), &str[1], 3);    // Put ternary absolute value starting at str[1]
    str[strlen(&str[1])] = '\0'; // Drop last digit
    return strtol(str, NULL, 3); // Read back result
}

你可以考虑用图或树状结构来解决这个问题。基本上生成的顶点数与要除以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

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