W jaki sposób można podzielić liczbę przez 3 bez używania *, /, +, -, %, operatorów?

Numer może być podpisany lub niepodpisany.

Jest to prosta funkcja, która wykonuje żądaną operację. Wymaga to jednak +operatora, więc wystarczy, że dodasz wartości za pomocą operatorów bitowych:

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

Jak skomentował Jim, działa to, ponieważ:

• n = 4 * a + b
• n / 3 = a + (a + b) / 3

• Tak sum += a, n = a + bi iterate

• Kiedy a == 0 (n < 4), sum += floor(n / 3);tj. 1,if n == 3, else 0

Warunki idiotyczne wymagają idiotycznego rozwiązania:

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

Jeśli potrzebna jest również część dziesiętna, po prostu zadeklaruj resultjako doublei dodaj do niej wynik fmod(number,divisor).

Wyjaśnienie, jak to działa

1. Do fwritepisze numberbajtów (liczba wynosi 123456 w powyższym przykładzie).
2. rewind resetuje wskaźnik pliku na początek pliku.
3. freadodczytuje maksymalnie number„rekordy” divisordługości z pliku i zwraca liczbę odczytanych elementów.

Jeśli napiszesz 30 bajtów, a następnie ponownie odczytasz plik w jednostkach 3, otrzymasz 10 „jednostek”. 30/3 = 10

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

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

Możesz użyć (zależnego od platformy) zestawu wbudowanego, np. Dla x86: (działa również dla liczb ujemnych)

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

Użyj itoa, aby przekonwertować na podstawowy ciąg 3. Upuść ostatni trit i przekonwertuj z powrotem na bazę 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
}

(uwaga: patrz Edycja 2 poniżej, aby uzyskać lepszą wersję!)

Nie jest to tak trudne, jak się wydaje, ponieważ powiedziałeś „bez użycia operatorów [..] +[..] ”. Zobacz poniżej, jeśli chcesz zabronić używania tej postaci razem.+

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

a potem po prostu powiedzieć, div_by(100,3)podzielić 100przez 3.

Edycja : Możesz także kontynuować i zastąpić ++operatora:

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

Edit 2: Nieco szybsza wersja bez użycia jakiegokolwiek operatora, który zawiera +, -, *, /, % znaki .

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

Używamy pierwszego argumentu addfunkcji, ponieważ nie możemy wskazać typu wskaźników bez użycia *znaku, z wyjątkiem list parametrów funkcji, w których składnia type[]jest identyczna type* const.

FWIW, możesz łatwo wdrożyć funkcję mnożenia za pomocą podobnej sztuczki, aby użyć 0x55555556sztuczki zaproponowanej przez AndreyT :

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

Jest to łatwo możliwe na komputerze Setun .

Aby podzielić liczbę całkowitą przez 3, przesuń w prawo o 1 miejsce .

Nie jestem jednak pewien, czy jest możliwe zaimplementowanie zgodnego kompilatora C na takiej platformie. Być może będziemy musieli nieco rozciągnąć reguły, na przykład interpretować „co najmniej 8 bitów” jako „zdolne do utrzymania co najmniej liczb całkowitych od -128 do +127”.

Skoro pochodzi od Oracle, to co powiesz na tabelę wyszukiwania wstępnie obliczonych odpowiedzi. :-RE

Oto moje rozwiązanie:

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

Po pierwsze, zwróć uwagę na to

1/3 = 1/4 + 1/16 + 1/64 + ...

Teraz reszta jest prosta!

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

Teraz wszystko, co musimy zrobić, to zsumować te nieco przesunięte wartości a! Ups! Nie możemy jednak dodawać, więc zamiast tego będziemy musieli napisać funkcję dodawania za pomocą bitowych operatorów! Jeśli znasz się na nieco bitowych operatorach, moje rozwiązanie powinno wyglądać dość prosto ... ale na wszelki wypadek, przejdę przez przykład na końcu.

Kolejną rzeczą do odnotowania jest to, że najpierw przesuwam w lewo o 30! Ma to na celu upewnienie się, że ułamki nie zostaną zaokrąglone.

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!

To po prostu dodatek, którego nauczyłeś się jako dziecko!

111
 1011
+0110
-----
10001

Ta implementacja nie powiodła się, ponieważ nie możemy dodać wszystkich warunków równania:

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

Załóżmy zatem, że reslut div_by_3(a)= x x <= floor(f(a, i)) < a / 3. Kiedy a = 3kotrzymujemy błędną odpowiedź.

Aby podzielić liczbę 32-bitową przez 3, można ją pomnożyć, 0x55555556a następnie pobrać 32 górne bity wyniku 64-bitowego.

Teraz pozostaje tylko zaimplementować mnożenie za pomocą operacji bitowych i przesunięć ...

Jeszcze inne rozwiązanie. Powinno to obsługiwać wszystkie liczby całkowite (w tym liczby całkowite ujemne) oprócz wartości minimalnej liczby całkowitej, która musiałaby być traktowana jako wyjątek zakodowany na stałe. Zasadniczo robi to dzielenie przez odejmowanie, ale tylko przy użyciu operatorów bitowych (shift, xor i & i dopełnianie). Dla większej prędkości odejmuje 3 * (malejące moce 2). W c # wykonuje około 444 z tych wywołań DivideBy3 na milisekundę (2,2 sekundy na 1 000 000 podziałów), więc nie jest strasznie powolny, ale nie jest tak szybki jak zwykłe x / 3. Dla porównania, dobre rozwiązanie Coodeya jest około 5 razy szybsze niż to.

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

To jest c #, ponieważ miałem to pod ręką, ale różnice w stosunku do c powinny być niewielkie.

To naprawdę bardzo proste.

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;

(Oczywiście pominąłem część programu ze względu na zwięzłość). Jeśli programista zmęczy się pisaniem tego wszystkiego, jestem pewien, że mógłby napisać osobny program, aby go wygenerować. Zdarza mi się wiedzieć o pewnym operatorze /, co znacznie uprościłoby jego pracę.

Korzystanie z liczników to podstawowe rozwiązanie:

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

Łatwo jest również wykonać funkcję modułu, sprawdź komentarze.

Ten jest klasycznym algorytmem podziału w bazie 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);
}

Napisz program w Pascal i użyj DIVoperatora.

Ponieważ pytanie jest oznaczone do, prawdopodobnie możesz napisać funkcję w Pascal i wywołać ją ze swojego programu w C; metoda ta jest specyficzna dla systemu.

Ale oto przykład, który działa na moim systemie Ubuntu z Free Pascal fp-compiler zainstalowanym pakietem . (Robię to z czysto upartego uporu; nie twierdzę, że jest to przydatne).

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

Budować:

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

Przykładowe wykonanie:

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

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

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

Nie sprawdziłem krzyżowo, czy ta odpowiedź jest już opublikowana. Jeśli program musi zostać rozszerzony na liczby zmiennoprzecinkowe, liczby można pomnożyć przez 10 * potrzebną liczbę dokładności, a następnie ponownie zastosować następujący kod.

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

To powinno działać dla każdego dzielnika, nie tylko trzech. Obecnie tylko dla niepodpisanych, ale rozszerzenie go na podpisane nie powinno być takie trudne.

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

Czy oszustwo byłoby używać /operatora „za kulisami” za pomocą evali łączenia łańcuchów?

Na przykład w Javacript możesz to zrobić

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

Korzystanie z BC Math w PHP :

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

MySQL (to wywiad z Oracle)

> SELECT 12345 DIV 3;

Pascal :

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

język asemblera x86-64:

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

Najpierw wymyśliłem.

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

EDYCJA: Przepraszam, nie zauważyłem tagu C. Ale możesz użyć pomysłu na formatowanie ciągów, tak myślę ...

Poniższy skrypt generuje program C, który rozwiązuje problem bez użycia operatorów * / + - %:

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

Korzystanie z kalkulatora liczb Hacker's Delight Magic

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

Gdzie fma jest standardową funkcją biblioteki zdefiniowaną w math.hnagłówku.

Co powiesz na to podejście (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;
    }

Myślę, że poprawna odpowiedź to:

Dlaczego nie miałbym używać operatora podstawowego do wykonania podstawowej operacji?

Rozwiązanie wykorzystujące funkcję biblioteki fma () , działa dla dowolnej liczby dodatniej:

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

Zobacz moją kolejną odpowiedź .

Użyj cblas , zawartych w ramach Accelerate systemu OS X.

[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

Ogólnie rozwiązaniem tego byłoby:

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

Pierwszy:

x/3 = (x/4) / (1-1/4)

Następnie wymyśl, jak rozwiązać 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))

zy = 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)
}

Chociaż używa +, ale ktoś już implementuje dodawanie bitowe op.