c - *,/,+,-,% ऑपरेटरों का उपयोग किए बिना 3 से एक संख्या विभाजित करें




math division (20)

32-बिट संख्या को 3 से विभाजित करने के लिए इसे 0x55555556 गुणा कर सकते हैं और फिर 64 बिट परिणाम के ऊपरी 32 बिट्स ले सकते हैं।

अब जो कुछ करने के लिए बाकी है, वह बिट ऑपरेशंस और शिफ्ट का उपयोग करके गुणा को कार्यान्वित करना है ...

* , / , + , - % , ऑपरेटरों का उपयोग किये बिना आप 3 से एक संख्या को कैसे विभाजित करेंगे?

संख्या पर हस्ताक्षर या हस्ताक्षर किए जा सकते हैं।

आधार 3 स्ट्रिंग में कनवर्ट करने के लिए itoa का उपयोग करें। अंतिम 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
}

इस दृष्टिकोण के बारे में (सी #)? 

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

ओएस एक्स के त्वरित ढांचे के हिस्से के रूप में शामिल cblas उपयोग करें। 

[02:31:59] [[email protected] ~]$ 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] [[email protected] ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031

क्या यह eval और स्ट्रिंग concatenation का उपयोग कर / दृश्यों के पीछे "दृश्यों के पीछे" प्रयोग करने के लिए धोखा दे रहा होगा?

उदाहरण के लिए, जावक्रिप्ट में, आप कर सकते हैं 

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

चूंकि यह ओरेकल से है, पूर्व गणना उत्तरों के लुकअप टेबल के बारे में कैसे। :-D

निम्न स्क्रिप्ट एक सी प्रोग्राम उत्पन्न करती है जो ऑपरेटर * / + - % का उपयोग किये बिना समस्या हल करती है: 

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

पास्कल में प्रोग्राम लिखें और DIV ऑपरेटर का उपयोग करें।

चूंकि प्रश्न c टैग किया c , इसलिए आप शायद पास्कल में एक फ़ंक्शन लिख सकते हैं और इसे अपने सी प्रोग्राम से कॉल कर सकते हैं; ऐसा करने की विधि सिस्टम-विशिष्ट है।

लेकिन यहां एक उदाहरण है जो मेरे उबंटू सिस्टम पर फ्री पास्कल 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

फिर भी एक और समाधान। यह एक इंट के न्यूनतम मूल्य को छोड़कर सभी चींटियों (नकारात्मक इट्स सहित) को संभालना चाहिए, जिसे हार्ड कोड किए गए अपवाद के रूप में संभालने की आवश्यकता होगी। यह मूल रूप से घटाव द्वारा विभाजन करता है लेकिन केवल बिट ऑपरेटर (शिफ्ट, एक्सओआर, और पूरक) का उपयोग करता है। तेज गति के लिए, यह 3 * घटाता है (2 की घटती शक्तियां)। सी # में, यह प्रति मिलीसेकंड (1,000,000 विभाजन के लिए 2.2 सेकंड) के इन DivideBy3 कॉलों में से 444 निष्पादित करता है, इसलिए भयभीत रूप से धीमा नहीं होता है, लेकिन एक साधारण x / 3 जितना तेज़ नहीं होता है। तुलनात्मक रूप से, कोडेई का अच्छा समाधान इस से लगभग 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;
}

यह सी # है क्योंकि मेरे पास यह आसान था, लेकिन सी से मतभेद मामूली होना चाहिए।

बेवकूफ स्थितियों को एक बेवकूफ समाधान के लिए बुलाओ: 

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

यदि दशमलव भाग की भी आवश्यकता है, तो परिणाम को fmod(number,divisor) और fmod(number,divisor) के परिणाम में जोड़ें।

यह कैसे काम करता है इसका स्पष्टीकरण

  1. fwrite number बाइट लिखता है (ऊपर उदाहरण में 123456 संख्या)।
  2. rewind फ़ाइल पॉइंटर फ़ाइल के सामने रीसेट करता है।
  3. fread अधिकतम number "रिकॉर्ड्स" पढ़ता है जो फ़ाइल से लंबाई में divisor हैं, और इसे पढ़ने वाले तत्वों की संख्या देता है।

यदि आप 30 बाइट लिखते हैं तो फ़ाइल को 3 की इकाइयों में वापस पढ़ें, आपको 10 "इकाइयां" मिलती हैं। 30/3 = 10

मेरा समाधान यहाँ है: 

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

अब हमें बस इतना करना है कि इन बिट्स को एक साथ स्थानांतरित किया गया है! ऊप्स! हालांकि हम जोड़ नहीं सकते हैं, इसलिए इसके बजाय, हमें बिट-वार ऑपरेटरों का उपयोग करके एक ऐड फ़ंक्शन लिखना होगा! यदि आप बिट-वार ऑपरेटरों से परिचित हैं, तो मेरा समाधान काफी सरल दिखना चाहिए ... लेकिन बस मामले में आप नहीं हैं, मैं अंत में एक उदाहरण के माध्यम से चलना होगा।

ध्यान देने योग्य एक और बात यह है कि पहले मैंने 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 <= floor(f(a, i)) < a / 3 का div_by_3(a) । जब a = 3k , हमें गलत जवाब मिलता है।

यह आधार 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);
}

यह एक साधारण कार्य है जो वांछित ऑपरेशन करता है। लेकिन इसके लिए + ऑपरेटर की आवश्यकता है, इसलिए आप बस इतना करना चाहते हैं कि बिट-ऑपरेटरों के साथ मान जोड़ना है: 

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

यह किसी भी divisor के लिए काम करना चाहिए, न केवल तीन। वर्तमान में केवल हस्ताक्षरित के लिए, लेकिन हस्ताक्षर करने के लिए इसे विस्तारित करना मुश्किल नहीं होना चाहिए। 

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

सबसे पहले मैं साथ आया हूँ। 

irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub('   ', ' ').size }
=> #<Proc:[email protected](irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222

संपादित करें: क्षमा करें, मैंने टैग C नोटिस नहीं किया था। लेकिन आप स्ट्रिंग स्वरूपण के बारे में विचार का उपयोग कर सकते हैं, मुझे लगता है ...

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

मेरा दूसरा जवाब देखें ।

Setun कंप्यूटर पर यह आसानी से संभव है ।

3 से एक पूर्णांक विभाजित करने के लिए, 1 स्थान से दाएं स्थानांतरित करें ।

मुझे यकीन नहीं है कि इस तरह के मंच पर एक अनुरूप सी संकलक को लागू करना सख्ती से संभव है या नहीं। हमें नियमों को थोड़ा सा विस्तार करना पड़ सकता है, जैसे "कम से कम 8 बिट्स" को "128 से +127 तक कम से कम पूर्णांक रखने में सक्षम" की व्याख्या करना। 

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

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

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





c   math   division  


division