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

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


当前回答

这真的很简单。

if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;

(当然,为了简洁起见,我省略了一些程序。)如果程序员厌倦了把这些都输入,我相信他或她可以编写一个单独的程序来为他生成这些。我碰巧认识一个能大大简化他工作的人。

其他回答

这是经典的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);
}

这应该适用于任何除数,而不仅仅是3。目前仅适用于unsigned,但将其扩展到signed应该没有那么困难。

#include <stdio.h>

unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do      {
        one = ~two & bor;
        two ^= bor;
        bor = one<<1;
        } while (one);
return two;
}

unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;

if (!bot || top < bot) return 0;

for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;

for (result=0; shift--; bot >>= 1 ) {
        result <<=1;
        if (top >= bot) {
                top = sub(top,bot);
                result |= 1;
                }
        }
return result;
}

int main(void)
{
unsigned arg,val;

for (arg=2; arg < 40; arg++) {
        val = bitdiv(arg,3);
        printf("Arg=%u Val=%u\n", arg, val);
        }
return 0;
}

下面的脚本生成了一个C程序,可以在不使用运算符* / + - %的情况下解决这个问题:

#!/usr/bin/env python3

print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')

for i in range(-2**31, 2**31):
    print('    if(input == %d) return %d;' % (i, i / 3))


print(r'''
    return 42; // impossible
}
int main()
{
    const int32_t number = 8;
    printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')

这是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

使用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
}