将数字除以3而不使用*,/,+, - ,%运算符

ivel 发布于 2019-01-24 c 最后更新 2019-01-24 18:43 145 浏览

如何在不使用*/+-%,操作员的情况下将数字除以3? 该号码可以是有符号的或无符号的。

已邀请:

dodit

赞同来自:

非常有趣,没有一个通用部门回答:

/* 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;
}
在其中一个答案中已经给出了按位添加,因此跳过它。

eomnis

赞同来自:

首先,我想出了。

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

wet

赞同来自:

好'OL bc

$ num=1337; printf "scale=5;${num}\x2F3;\n" | bc
445.66666

gut

赞同来自:

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

walias

赞同来自:

好吧,我想我们都同意这不是一个现实世界的问题。所以只是为了好玩,这里是如何使用Ada和多线程来做到这一点:

with Ada.Text_IO;
procedure Divide_By_3 is
protected type Divisor_Type is
      entry Poke;
      entry Finish;
   private
      entry Release;
      entry Stop_Emptying;
      Emptying : Boolean := False;
   end Divisor_Type;
protected type Collector_Type is
      entry Poke;
      entry Finish;
   private
      Emptying : Boolean := False;
   end Collector_Type;
task type Input is
   end Input;
   task type Output is
   end Output;
protected body Divisor_Type is
      entry Poke when not Emptying and Stop_Emptying'Count = 0 is
      begin
         requeue Release;
      end Poke;
      entry Release when Release'Count >= 3 or Emptying is
         New_Output : access Output;
      begin
         if not Emptying then
            New_Output := new Output;
            Emptying := True;
            requeue Stop_Emptying;
         end if;
      end Release;
      entry Stop_Emptying when Release'Count = 0 is
      begin
         Emptying := False;
      end Stop_Emptying;
      entry Finish when Poke'Count = 0 and Release'Count < 3 is
      begin
         Emptying := True;
         requeue Stop_Emptying;
      end Finish;
   end Divisor_Type;
protected body Collector_Type is
      entry Poke when Emptying is
      begin
         null;
      end Poke;
      entry Finish when True is
      begin
         Ada.Text_IO.Put_Line (Poke'Count'Img);
         Emptying := True;
      end Finish;
   end Collector_Type;
Collector : Collector_Type;
   Divisor : Divisor_Type;
task body Input is
   begin
      Divisor.Poke;
   end Input;
task body Output is
   begin
      Collector.Poke;
   end Output;
Cur_Input : access Input;
-- Input value:
   Number : Integer := 18;
begin
   for I in 1 .. Number loop
      Cur_Input := new Input;
   end loop;
   Divisor.Finish;
   Collector.Finish;
end Divide_By_3;

jvitae

赞同来自:

在Pascal中编写程序并使用DIV运算符。 由于问题标记为,您可以在Pascal中编写一个函数并从C程序中调用它;这样做的方法是系统特定的。 但这是一个在我的Ubuntu系统上运行的示例,其中安装了Free Pascal fp-compiler包。 (我这样做是因为完全错位的固执;我没有声称这是有用的。) divide_by_3.pas

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.
main.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

sit_in

赞同来自:

(注意:请参阅下面的编辑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函数的第一个参数,因为除了函数参数列表之外我们不能表示不使用*字符的指针类型,其中语法type[]type* const相同。 FWIW,您可以使用类似的技巧轻松实现乘法函数,以使用AndreyT提出的0x55555556技巧:
int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}

znemo

赞同来自:

使用计数器是一个基本解决方案

int DivBy3(int num) {
    int result = 0;
    int counter = 0;
    while (1) {
        if (num == counter)       //Modulus 0
            return result;
        counter = abs(~counter);  //++counter
if (num == counter)       //Modulus 1
            return result;
        counter = abs(~counter);  //++counter
if (num == counter)       //Modulus 2
            return result;
        counter = abs(~counter);  //++counter
result = abs(~result);    //++result
    }
}
执行模数函数也很容易,检查注释。

emagni

赞同来自:

为什么我们不应用大学学习的定义?结果可能效率低但是很清楚,因为乘法只是递归减法和减法是加法,然后可以通过递归xor /和逻辑端口组合来执行加法。

#include <stdio.h>
int add(int a, int b){
   int rc;
   int carry;
   rc = a ^ b; 
   carry = (a & b) << 1;
   if (rc & carry) 
      return add(rc, carry);
   else
      return rc ^ carry; 
}
int sub(int a, int b){
   return add(a, add(~b, 1)); 
}
int div( int D, int Q )
{
/* lets do only positive and then
 * add the sign at the end
 * inversion needs to be performed only for +Q/-D or -Q/+D
 */
   int result=0;
   int sign=0;
   if( D < 0 ) {
      D=sub(0,D);
      if( Q<0 )
         Q=sub(0,Q);
      else
         sign=1;
   } else {
      if( Q<0 ) {
         Q=sub(0,Q);
         sign=1;
      } 
   }
   while(D>=Q) {
      D = sub( D, Q );
      result++;
   }
/*
* Apply sign
*/
   if( sign )
      result = sub(0,result);
   return result;
}
int main( int argc, char ** argv ) 
{
    printf( "2 plus 3=%d\n", add(2,3) );
    printf( "22 div 3=%d\n", div(22,3) );
    printf( "-22 div 3=%d\n", div(-22,3) );
    printf( "-22 div -3=%d\n", div(-22,-3) );
    printf( "22 div 03=%d\n", div(22,-3) );
    return 0;
}
正如有人所说......首先让这项工作成功。请注意,算法应该适用于负Q ...

zomnis

赞同来自:

那么你可以考虑使用图形/树状结构来解决问题。基本上生成与要除以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
这显然可以优化,复杂性取决于你的数量有多大,但是它可以提供你可以做++和 - 的工作。 它只计算冷却器一样好。

iaut

赞同来自:

#!/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

punde

赞同来自:

通常,解决方案是: log(pow(exp(numerator),pow(denominator,-1)))

oiusto

赞同来自:

使用itoa转换为基数3字符串。删除最后一个trit并转换回基数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
}

ret

赞同来自:

PHP中使用BC Math

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

MySQL(这是Oracle的采访)
> SELECT 12345 DIV 3;

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

x86-64汇编语言:
mov  r8, 3
xor  rdx, rdx   
mov  rax, 12345
idiv r8

wanimi

赞同来自:

我会使用此代码来划分所有正数,非浮点数。基本上你想要将除数位对齐到左边以匹配被除数位。对于被除数的每个部分(除数的大小),您要检查以确定被除数的部分是否大于除数,那么您想要在第一个注册器中向左移位然后移位OR。这个概念最初创建于2004年(我相信Standford),这是一个使用该概念的C版本。注意:(我修改了一下)

int divide(int a, int b)
{
    int c = 0, r = 32, i = 32, p = a + 1;
    unsigned long int d = 0x80000000;
while ((b & d) == 0)
    {
        d >>= 1;
        r--;
    }
while (p > a)
    {
        c <<= 1;
        p = (b >> i--) & ((1 << r) - 1);
        if (p >= a)
            c |= 1;
    }
    return c; //p is remainder (for modulus)
}
用法示例:
int n = divide( 3, 6); //outputs 2

nqui

赞同来自:

这是我祖父在我还是个子元素时教给我的一种方法。它需要+和/运算符,但它使计算变得容易。 将各个数字加在一起,然后查看它是否是3的倍数。 但是这种方法适用于12以上的数字。 示例:36, 3 + 6 = 9是3的倍数。 42, 4 + 2 = 6是3的倍数。

yautem

赞同来自:

这是执行所需操作的simple function。但是它需要+运算符,所以你要做的只是用位运算符添加值:

// 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
  • So sum += a, n = a + b,并迭代
  • a == 0 (n < 4)sum += floor(n / 3);即1,if n == 3, else 0

qanimi

赞同来自:

如果你提醒自己标准的学校分割方法并用二进制方法进行,你会发现在3的情况下你只能分割和减去一组有限的值(在这种情况下从0到5)。这些可以用switch语句来处理,以摆脱算术运算符。

static unsigned lamediv3(unsigned n)
{
  unsigned result = 0, remainder = 0, mask = 0x80000000;
// Go through all bits of n from MSB to LSB.
  for (int i = 0; i < 32; i++, mask >>= 1)
  {
    result <<= 1;
    // Shift in the next bit of n into remainder.
    remainder = remainder << 1 | !!(n & mask);
// Divide remainder by 3, update result and remainer.
    // If remainder is less than 3, it remains intact.
    switch (remainder)
    {
    case 3:
      result |= 1;
      remainder = 0;
      break;
case 4:
      result |= 1;
      remainder = 1;
      break;
case 5:
      result |= 1;
      remainder = 2;
      break;
    }
  }
return result;
}
#include <cstdio>
int main()
{
  // Verify for all possible values of a 32-bit unsigned integer.
  unsigned i = 0;
do
  {
    unsigned d = lamediv3(i);
if (i / 3 != d)
    {
      printf("failed for %u: %u != %u\n", i, d, i / 3);
      return 1;
    }
  }
  while (++i != 0);
}

psequi

赞同来自:

所有答案可能都不是面试官喜欢听到的: 我的答案:

"I would never do that, who will me pay for such silly things. Nobody will have an advantage on that, its not faster, its only silly. Prozessor designers have to know that, but this must then work for all numbers, not only for division by 3"

ut_et

赞同来自:

要将32位数除以3,可以将其乘以0x55555556,然后取64位结果的高32位。 现在剩下要做的就是使用位操作和移位来实现乘法......

hquas

赞同来自:

使用Hacker's Delight Magic number calculator

int divideByThree(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}
其中fmamath.h标头中定义的标准库函数。

frem

赞同来自:

如果我们认为div不是正交的/

def divBy3(n):
    return n.__div__(3)
print divBy3(9), 'or', 9//3

uid

赞同来自:

log(pow(exp(number),0.33333333333333333333)) /* :-) */

xid

赞同来自:

白痴状况需要一种愚蠢的解决方案:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    FILE * fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char * buf = calloc(number,1);
    fwrite(buf,number,1,fp);
    rewind(fp);
    int result=fread(buf,divisor,number,fp);
    printf("%d / %d = %d", number, divisor, result);
    free(buf);
    fclose(fp);
    return 0;
}
如果还需要小数部分,只需将result声明为double并将fmod(number,divisor)的结果添加到其中。 解释它是如何工作的
  1. fwrite写入number个字节(上例中的数字为123456)。
  2. rewind将文件指针重置为文件的前面。
  3. fread从文件中读取长度为divisornumber“记录”的最大值,并返回它读取的元素数。
如果你写30个字节,然后以3为单位读回文件,你得到10“单位”。 30/3 = 10

zrerum

赞同来自:

我认为正确的答案是: 为什么我不使用基本操作员进行基本操作?

znon

赞同来自:

Setun computer上很容易实现。 要将整数除以3,请使用shift right by 1 place。 我不确定是否可以在这样的平台上实现一致的C编译器。我们可能不得不稍微延长规则,比如将“至少8位”解释为“能够保持至少从-128到+127的整数”。

xquis

赞同来自:

#include <stdio.h>
typedef struct { char a,b,c; } Triple;
unsigned long div3(Triple *v, char *r) {
  if ((long)v <= 2)  
    return (unsigned long)r;
  return div3(&v[-1], &r[1]);
}
int main() {
  unsigned long v = 21; 
  int r = div3((Triple*)v, 0); 
  printf("%ld / 3 = %d\n", v, r); 
  return 0;
}

sed_et

赞同来自:

使用Linux shell脚本:

#include <stdio.h>
int main()
{
    int number = 30;
    char command[25];
    snprintf(command, 25, "echo $((%d %c 3)) ", number, 47);
    system( command );
    return 0;
}
See my another answer

dquia

赞同来自:

似乎没有人提到以二进制表示的3的除法标准 - 偶数位的和应该等于奇数位的总和(类似于十进制中的11的标准)。在Check if a number is divisible by 3下有使用此技巧的解决方案。 我想这是Michael Burr编辑提到的可能重复。

mest

赞同来自:

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

veos

赞同来自:

第一:

x/3 = (x/4) / (1-1/4)
然后弄清楚如何解决x /(1 - y):
x/(1-1/y)
  = x * (1+y) / (1-y^2)
  = x * (1+y) * (1+y^2) / (1-y^4)
  = ...
  = x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
  = x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))
y = 1/4:
int div3(int x) {
    x <<= 6;    // need more precise
    x += x>>2;  // x = x * (1+(1/2)^2)
    x += x>>4;  // x = x * (1+(1/2)^4)
    x += x>>8;  // x = x * (1+(1/2)^8)
    x += x>>16; // x = x * (1+(1/2)^16)
    return (x+1)>>8; // as (1-(1/2)^32) very near 1,
                     // we plus 1 instead of div (1-(1/2)^32)
}
虽然它使用了+,但有人已经通过按位运算实现了add

uid

赞同来自:

这将有效......

smegma$ curl http://www.wolframalpha.com/input/?i=14+divided+by+3 2>/dev/null | gawk 'match($0, /link to /input/\?i=([0-9.+-]+)/, ary) { print substr( $0, ary[1, "start"], ary[1, "length"] )}' 4.6666666666666666666666666666666666666666666666666666
用你的数字代替'14'和'3'。

xsit

赞同来自:

使用cblas,作为OS X的Accelerate框架的一部分。

[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>
int main() {
    float multiplicand = 123456.0;
    float multiplier = 0.333333;
    printf("%f * %f == ", multiplicand, multiplier);
    cblas_sscal(1, multiplier, &multiplicand, 1);
    printf("%f\n", multiplicand);
}
[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031

ut_est

赞同来自:

这是基数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);
}

hvelit

赞同来自:

您可以使用(依赖于平台的)内联汇编,例如,对于x86:(also works for negative numbers)

#include <stdio.h>
int main() {
  int dividend = -42, divisor = 5, quotient, remainder;
__asm__ ( "cdq; idivl %%ebx;"
          : "=a" (quotient), "=d" (remainder)
          : "a"  (dividend), "b"  (divisor)
          : );
printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
  return 0;
}

det

赞同来自:

其中InputValue是除以3的数字

SELECT AVG(NUM) 
  FROM (SELECT InputValue NUM from sys.dual
         UNION ALL SELECT 0 from sys.dual
         UNION ALL SELECT 0 from sys.dual) divby3

ut_sit

赞同来自:

这是我的解决方案:

public static int div_by_3(long a) {
    a <<= 30;
    for(int i = 2; i <= 32 ; i <<= 1) {
        a = add(a, a >> i);
    }
    return (int) (a >> 32);
}
public static long add(long a, long b) {
    long carry = (a & b) << 1;
    long sum = (a ^ b);
    return carry == 0 ? sum : add(carry, sum);
}
首先,请注意
1/3 = 1/4 + 1/16 + 1/64 + ...
现在,其余的都很简单!
a/3 = a * 1/3  
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
现在我们所要做的就是将这些位移值加在一起!哎呀!我们不能添加,所以相反,我们必须使用逐位运算符编写一个add函数!如果你熟悉逐位运算符,我的解决方案看起来应该很简单......但是如果你不是,我会在最后看一个例子。 另外需要注意的是,首先我向左移动30!这是为了确保分数不会四舍五入。
11 + 6
1011 + 0110  
sum = 1011 ^ 0110 = 1101  
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100  
Now you recurse!
1101 + 0100  
sum = 1101 ^ 0100 = 1001  
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000  
Again!
1001 + 1000  
sum = 1001 ^ 1000 = 0001  
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000  
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17  
carry = (0001 & 10000) << 1 = 0
Done!
它只是随身携带你小时候学到的东西!
111
 1011
+0110
-----
10001
此实现失败,因为我们无法添加等式的所有项:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
假设div_by_3(a) = x的重新连接,然后是x <= floor(f(a, i)) < a / 3。当a = 3k,我们得到错误的答案。

trerum

赞同来自:

既然它来自Oracle,那么预先计算出答案的查找表怎么样呢。 :-D

xhic

赞同来自:

通过使用eval和字符串连接来“幕后”使用/运算符会不会是作弊? 例如,在Javacript,你可以做到

function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}

tvel

赞同来自:

使用fma() library function的解决方案适用于任何正数:

#include <stdio.h>
#include <math.h>
int main()
{
    int number = 8;//Any +ve no.
    int temp = 3, result = 0;
    while(temp <= number){
        temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
        result = fma(result, 1, 1);
    } 
    printf("\n\n%d divided by 3 = %d\n", number, result);
}
See my another answer

uin

赞同来自:

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

amagni

赞同来自:

以下脚本生成一个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));
}
''')

benim

赞同来自:

这种方法怎么样(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;
    }

ysequi

赞同来自:

这真的很容易。

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;
(为了简洁起见,我当然省略了一些程序。)如果程序员厌倦了全部输入,我肯定他或她可以编写一个单独的程序来为他生成它。我碰巧知道某个操作员/会极大地简化他的工作。

ut_sed

赞同来自:

基数2中的3是11。 所以只需要在基地2比11做长分区(比如在中学)。在基地2比基地10更容易。 对于从最重要的位置开始的每个位位置: 确定前缀是否小于11。 如果输出0。 如果它不是输出1,则替换前缀位以进行适当的更改。只有三种情况:

 11xxx ->    xxx    (ie 3 - 3 = 0)
100xxx ->   1xxx    (ie 4 - 3 = 1)
101xxx ->  10xxx    (ie 5 - 3 = 2)
所有其他前缀都无法访问。 重复直到最低位位置,你就完成了。

gut

赞同来自:

这适用于任何除数,而不仅仅是三个。目前仅用于未签名,但将其扩展为签名应该不那么困难。

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

out

赞同来自:

没有反复核对这个答案是否已经发布。如果程序需要扩展为浮点数,则可以将数字乘以10 *所需的精度数,然后再次应用以下代码。

#include <stdio.h>
int main()
{
    int aNumber = 500;
    int gResult = 0;
int aLoop = 0;
int i = 0;
    for(i = 0; i < aNumber; i++)
    {
        if(aLoop == 3)
        {
           gResult++;
           aLoop = 0;
        }  
        aLoop++;
    }
printf("Reulst of %d / 3 = %d", aNumber, gResult);
return 0;
}

nodit

赞同来自:

又一个解决方案。这应该处理除int的最小值之外的所有整数(包括负整数),这需要作为硬编码异常处理。这基本上通过减法除法,但仅使用位运算符(shift,xor,&和补码)。为了更快的速度,它减去3 *(减少2的幂)。在c#中,它每毫秒执行大约444个DivideBy3调用(1,000,000个分频为2.2秒),所以不是非常慢,但没有像简单的x / 3那样快。相比之下,Coodey的优秀解决方案比这个快5倍。

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的差异应该是次要的。