Вы можете использовать встроенную сборку (зависит от платформы), например, для x86: (также работает для отрицательных чисел)

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

Используйте 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
}

(примечание: см. "Правка 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: немного более быстрая версия без использования оператора, содержащего символы _9 _, _ 10 _, _ 11 _, _ 12 _, _ 13_ .

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, вы можете легко реализовать функцию умножения, используя аналогичный трюк, чтобы использовать трюк 0x55555556, предложенный AndreyT:

int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}

Это легко сделать на компьютере Setun.

Чтобы разделить целое число на 3, сдвиньте вправо на 1 место.

Однако я не уверен, возможно ли реализовать соответствующий компилятор C на такой платформе. Возможно, нам придется немного расширить правила, например, интерпретировать «минимум 8 бит» как «способный содержать как минимум целые числа от -128 до +127».

Поскольку это от Oracle, как насчет таблицы поиска предварительно рассчитанных ответов. :-D

Вот мое решение:

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

Теперь все, что нам нужно сделать, это сложить эти сдвинутые на бит значения a! Ой! Однако мы не можем добавить, поэтому вместо этого нам придется написать функцию добавления, используя битовые операторы! Если вы знакомы с поразрядными операторами, мое решение должно выглядеть довольно простым ... но на случай, если вы этого не сделаете, я рассмотрю пример в конце.

Еще стоит отметить, что сначала я сдвигаюсь влево на 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, мы получаем неправильный ответ.

Чтобы разделить 32-битное число на 3, его можно умножить на 0x55555556, а затем взять старшие 32 бита 64-битного результата.

Теперь все, что осталось сделать, это реализовать умножение с помощью битовых операций и сдвигов ...

Еще одно решение. Это должно обрабатывать все целые числа (включая отрицательные целые числа), кроме минимального значения целого числа, которое необходимо обрабатывать как жестко закодированное исключение. Это в основном выполняет деление на вычитание, но только с использованием битовых операторов (сдвиги, xor, & и дополнение). Для большей скорости он вычитает 3 * (уменьшение степени 2). В C # он выполняет около 444 этих вызовов DivideBy3 в миллисекунду (2,2 секунды для 1000000 делений), поэтому не ужасно медленно, но и близко не так быстро, как простой 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 должны быть незначительными.

Это действительно очень просто.

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;

(Я, конечно, опустил часть программы для краткости.) Если программист устанет набирать все это, я уверен, что он или она могли бы написать отдельную программу, чтобы сгенерировать это для него. Я знаю одного оператора /, который значительно упростил бы его работу.

Использование счетчиков - базовое решение:

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

Также легко выполнить модульную функцию, проверьте комментарии.

Это классический алгоритм деления по основанию 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);
}

Напишите программу на Паскале и используйте оператор DIV.

Поскольку вопрос помечен как c, вы, вероятно, можете написать функцию на Паскале и вызовите ее из вашей программы на 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

Не проверял, опубликован ли уже этот ответ. Если программа должна быть расширена до чисел с плавающей запятой, числа можно умножить на 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;
}

Это должно работать для любого делителя, а не только для трех. В настоящее время только для неподписанных, но расширить его до подписанных не должно быть так сложно.

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

Было бы обманом использовать оператор / «за кулисами», используя eval и конкатенацию строк?

Например, в Javacript вы можете сделать

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

Используя BC Math в PHP:

<?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

Первое, что я придумал.

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. Но я думаю, вы можете использовать идею форматирования строк ...

Следующий сценарий генерирует программу на языке 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));
}
''')

Использование Калькулятора чисел Hacker's Delight Magic

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

Где fma - это стандартная библиотечная функция, определенная в заголовке math.h.

Как насчет этого подхода (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;
    }

Думаю, правильный ответ:

Почему бы мне не использовать базовый оператор для выполнения основной операции?

Решение, использующее библиотечную функцию fma (), работает для любого положительного числа:

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

См. еще один мой ответ.

Используйте 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

Как правило, решение этой проблемы:

log(pow(exp(numerator),pow(denominator,-1)))

Первый:

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 by bitwise op.

Хорошо, я думаю, мы все согласны с тем, что это не проблема реального мира. Итак, просто для удовольствия, вот как это сделать с помощью 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;

Довольно удивленный, никто не ответил общим делением:

/* 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;
}

Поразрядное сложение уже было указано в одном из ответов, поэтому пропустите его.

Вероятно, не все ответы совпадают с тем, что хотел услышать интервьюер:

Мой ответ:

«Я бы никогда этого не сделал, кто будет мне платить за такие глупые вещи. Ни у кого не будет преимущества в этом, это не быстрее, это только глупо. Дизайнеры Prozessor должны это знать, но тогда это должно работать для всех чисел, а не только для деления на 3 "

Почему бы нам просто не применить определение, полученное в колледже? Результат может быть неэффективным, но очевидным, поскольку умножение - это просто рекурсивное вычитание, а вычитание - это сложение, тогда сложение может быть выполнено с помощью комбинации рекурсивного 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 ...

Если вы напомните себе стандартный школьный метод деления и сделаете это в двоичном формате, вы обнаружите, что в случае 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);
}

Где 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

если учесть, что __div__ не является орфографическим /

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

print divBy3(9), 'or', 9//3

3 в базе 2 равно 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)

Все остальные префиксы недоступны.

Повторяйте до самого нижнего положения бита, и все готово.

Кажется, никто не упомянул критерий деления для 3, представленный в двоичном формате - сумма четных цифр должна равняться сумме нечетных цифр (аналогично критерию 11 в десятичной системе). Есть решения, использующие этот трюк в разделе Проверить, делится ли число на 3 < / а>.

Я бы использовал этот код для деления всех положительных чисел, отличных от чисел с плавающей запятой. В основном вы хотите выровнять биты делителя влево, чтобы они соответствовали битам делимого. Для каждого сегмента дивиденда (размер делителя) вы хотите проверить, больше ли сегмент дивиденда, чем делитель, тогда вы хотите сдвинуть влево, а затем ИЛИ в первом регистраторе. Эта концепция была первоначально создана в 2004 году (я полагаю, стандартная версия). Вот версия 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

Это будет работать:

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» своими числами.

Вот он в 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. Затем продолжайте соединять каждую непарную вершину с двумя другими вершинами.

Грубый псевдокод:

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

Очевидно, что это можно оптимизировать, а сложность зависит от того, насколько велико ваше число, но он должен работать, если вы можете использовать ++ и -. Это все равно, что считать только круче.

Используя сценарий оболочки Linux:

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

См. другой мой ответ.

Старый добрый bc:

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

Вот метод, которому дедушка научил меня, когда я был ребенком. Для этого требуются операторы + и /, но это упрощает вычисления.

Сложите отдельные цифры вместе и посмотрите, кратно ли оно трем.

Но этот метод работает для чисел выше 12.

Пример: 36,

3 + 6 = 9, что делится на 3.

42,

4 + 2 = 6, что делится на 3.