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

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


当前回答

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

用Pascal编写程序并使用DIV操作符。

因为问题被标记为c,你可以在Pascal中编写一个函数,然后在c程序中调用它;这样做的方法是特定于系统的。

但是这里有一个在我的Ubuntu系统上运行的例子,安装了Free Pascal fp-编译器包。(我这么做完全是出于不合时宜的固执;我不敢说这是有用的。)

divide_by_3。不是:

unit Divide_By_3;
interface
    function div_by_3(n: integer): integer; cdecl; export;
implementation
    function div_by_3(n: integer): integer; cdecl;
    begin
        div_by_3 := n div 3;
    end;
end.

c:

#include <stdio.h>
#include <stdlib.h>

extern int div_by_3(int n);

int main(void) {
    int n;
    fputs("Enter a number: ", stdout);
    fflush(stdout);
    scanf("%d", &n);
    printf("%d / 3 = %d\n", n, div_by_3(n));
    return 0;
}

构建:

fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main

示例执行:

$ ./main
Enter a number: 100
100 / 3 = 33

这是一个执行所需操作的简单函数。但是它需要+操作符,所以你所要做的就是用位操作符来加值:

// replaces the + operator
int add(int x, int y)
{
    while (x) {
        int t = (x & y) << 1;
        y ^= x;
        x = t;
    }
    return y;
}

int divideby3(int num)
{
    int sum = 0;
    while (num > 3) {
        sum = add(num >> 2, sum);
        num = add(num >> 2, num & 3);
    }
    if (num == 3)
        sum = add(sum, 1);
    return sum; 
}

正如吉姆评论的那样,这是可行的,因为:

N = 4 * a + b N / 3 = a + (a + b) / 3 sum += an = a + b,然后迭代 当a == 0 (n < 4)时,sum += floor(n / 3);即1,如果n == 3,否则为0

这是Python中的,基本上,字符串比较和一个状态机。

def divide_by_3(input):
  to_do = {}
  enque_index = 0
  zero_to_9 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  leave_over = 0
  for left_over in (0, 1, 2):
    for digit in zero_to_9:
      # left_over, digit => enque, leave_over
      to_do[(left_over, digit)] = (zero_to_9[enque_index], leave_over)
      if leave_over == 0:
        leave_over = 1
      elif leave_over == 1:
        leave_over = 2
      elif leave_over == 2 and enque_index != 9:
        leave_over = 0
        enque_index = (1, 2, 3, 4, 5, 6, 7, 8, 9)[enque_index]
  answer_q = []
  left_over = 0
  digits = list(str(input))
  if digits[0] == "-":
    answer_q.append("-")
  digits = digits[1:]
  for digit in digits:
    enque, left_over = to_do[(left_over, int(digit))]
    if enque or len(answer_q):
      answer_q.append(enque)
  answer = 0
  if len(answer_q):
    answer = int("".join([str(a) for a in answer_q]))
  return answer

3以2为底等于11。

所以只要做长除法(就像中学那样),以2 × 11为底。以2为底比以10为底更简单。

对于从最有效位开始的每个位位:

判断prefix是否小于11。

如果它是输出0。

如果不是输出1,则替换前缀位进行适当的更改。只有三种情况:

 11xxx ->    xxx    (ie 3 - 3 = 0)
100xxx ->   1xxx    (ie 4 - 3 = 1)
101xxx ->  10xxx    (ie 5 - 3 = 2)

所有其他前缀都不可达。

重复到最低位,你就完成了。