bit manipulation बिट-वार ऑपरेटर के साथ विभाजन को कार्यान्वित करें




bit-manipulation (9)

नीचे दी गई विधि बाइनरी विभाजन का कार्यान्वयन है क्योंकि दोनों संख्याएं सकारात्मक हैं। अगर घटाव चिंता का विषय है तो हम इसे बाइनरी ऑपरेटरों का उपयोग भी कर सकते हैं।

कोड

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator == 0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits>0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0 ? 1 : 0;
        subResult = (subResult << 1) |msbBit;
        if (subResult >= denominator) {
            subResult = subResult-denominator;
            qoutient = (qoutient << 1) | 1;
        }
        else {
            qoutient = qoutient << 1;
        }
        remainingBits--;
    }
    return qoutient;
}


-(int)getMaxBit:(int)inputNumber
{
    int maxBit =0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1 << i) ) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit += 1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit -bits);
}

मैं बिट-वार ऑपरेटरों का उपयोग करके विभाजन को कैसे कार्यान्वित कर सकता हूं (केवल 2 शक्तियों द्वारा विभाजित नहीं)?

विस्तार से इसका वर्णन करें।


विभाजन करने का मानक तरीका द्विआधारी लंबे विभाजन को कार्यान्वित करना है। इसमें घटाव शामिल है, इसलिए जब तक आप इसे बिट-वार ऑपरेशन के रूप में छूट नहीं देते, तो यह वही है जो आपको करना चाहिए। (ध्यान दें कि आप बिटवाई लॉजिकल ऑपरेशंस का उपयोग करके, बहुत ही थकाऊ रूप से घटाव को कार्यान्वित कर सकते हैं।)

संक्षेप में, यदि आप Q = N/D कर रहे हैं:

  1. N और D के सबसे महत्वपूर्ण लोगों को संरेखित करें।
  2. गणना t = (N - D);
  3. यदि (t >= 0) , तो Q से कम से कम महत्वपूर्ण बिट सेट करें, और N = t सेट करें।
  4. 1 से बाएं शिफ्ट N
  5. 1 से बाएं शिफ्ट Q
  6. चरण 2 पर जाएं।

आपको जितनी आवश्यकता हो उतनी आउटपुट बिट्स (fractional सहित) के लिए लूप, फिर चरण 1 में जो किया है उसे पूर्ववत करने के लिए अंतिम बदलाव लागू करें।


int remainder =0;

int division(int dividend, int divisor)
{
    int quotient = 1;

    int neg = 1;
    if ((dividend>0 &&divisor<0)||(dividend<0 && divisor>0))
        neg = -1;

    // Convert to positive
    unsigned int tempdividend = (dividend < 0) ? -dividend : dividend;
    unsigned int tempdivisor = (divisor < 0) ? -divisor : divisor;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1*neg;
    }
    else if (tempdividend < tempdivisor) {
        if (dividend < 0)
            remainder = tempdividend*neg;
        else
            remainder = tempdividend;
        return 0;
    }
    while (tempdivisor<<1 <= tempdividend)
    {
        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;
    }

    // Call division recursively
    if(dividend < 0)
        quotient = quotient*neg + division(-(tempdividend-tempdivisor), divisor);
    else
        quotient = quotient*neg + division(tempdividend-tempdivisor, divisor);
     return quotient;
 }


void main()
{
    int dividend,divisor;
    char ch = 's';
    while(ch != 'x')
    {
        printf ("\nEnter the Dividend: ");
        scanf("%d", &dividend);
        printf("\nEnter the Divisor: ");
        scanf("%d", &divisor);

        printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
        printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

        _getch();
    }
}

Bitwise ऑपरेटरों का उपयोग कर दो संख्याओं का विभाजन।

#include <stdio.h>

int remainder, divisor;

int division(int tempdividend, int tempdivisor) {
    int quotient = 1;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1;
    } else if (tempdividend < tempdivisor) {
        remainder = tempdividend;
        return 0;
    }   

    do{

        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;

     } while (tempdivisor <= tempdividend);


     /* Call division recursively */
    quotient = quotient + division(tempdividend - tempdivisor, divisor);

    return quotient;
} 


int main() {
    int dividend;

    printf ("\nEnter the Dividend: ");
    scanf("%d", &dividend);
    printf("\nEnter the Divisor: ");
    scanf("%d", &divisor);   

    printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
    printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
    getch();
}

पूर्णांक के लिए:

public class Division {

    public static void main(String[] args) {
        System.out.println("Division: " + divide(100, 9));
    }

    public static int divide(int num, int divisor) {
        int sign = 1;
        if((num > 0 && divisor < 0) || (num < 0 && divisor > 0))
            sign = -1;

        return divide(Math.abs(num), Math.abs(divisor), Math.abs(divisor)) * sign;
    }

    public static int divide(int num, int divisor, int sum) {
        if (sum > num) {
            return 0;
        }

        return 1 + divide(num, divisor, sum + divisor);
    }
}

डिवीजन ऑपरेटर के बिना विभाजन को कार्यान्वित करें: आपको घटाव शामिल करना होगा। लेकिन फिर यह ऐसा है जैसे आप इसे हाथ से करते हैं (केवल 2 के आधार पर)। संलग्न कोड एक छोटा सा कार्य प्रदान करता है जो वास्तव में करता है।

uint32_t udiv32(uint32_t n, uint32_t d) {
    // n is dividend, d is divisor
    // store the result in q: q = n / d
    uint32_t q = 0;

    // as long as the divisor fits into the remainder there is something to do
    while (n >= d) {
        uint32_t i = 0, d_t = d;
        // determine to which power of two the divisor still fits the dividend
        //
        // i.e.: we intend to subtract the divisor multiplied by powers of two
        // which in turn gives us a one in the binary representation 
        // of the result
        while (n >= (d_t << 1) && ++i)
            d_t <<= 1;
        // set the corresponding bit in the result
        q |= 1 << i;
        // subtract the multiple of the divisor to be left with the remainder
        n -= d_t;
        // repeat until the divisor does not fit into the remainder anymore
    }
    return q;
}

शिफ्ट के साथ सी के व्यवहार के बारे में सामान्य चेतावनी के साथ, यह int int के मूल आकार के बावजूद हस्ताक्षरित मात्रा के लिए काम करना चाहिए ...

static unsigned int udiv(unsigned int a, unsigned int b) {
  unsigned int c = 1, result = 0;

  if (b == 0) return (unsigned int)-1 /*infinity*/;

  while (((int)b > 0) && (b < a)) { b = b<<1; c = c<<1; }

  do {
    if (a >= b) { a -= b; result += c; }
    b = b>>1; c = c>>1;
  } while (c);

  return result;
}

यह समाधान पूरी तरह से काम करता है।

#include <stdio.h>

int division(int dividend, int divisor, int origdiv, int * remainder)
{
    int quotient = 1;

    if (dividend == divisor)
    {
        *remainder = 0;
        return 1;
    }

    else if (dividend < divisor)
    {
        *remainder = dividend;
        return 0;
    }

    while (divisor <= dividend)
    {
        divisor = divisor << 1;
        quotient = quotient << 1;
    }

    if (dividend < divisor)
    {
        divisor >>= 1;
        quotient >>= 1;
    }

    quotient = quotient + division(dividend - divisor, origdiv, origdiv, remainder);

    return quotient;
}

int main()
{
    int n = 377;
    int d = 7;
    int rem = 0;

    printf("Quotient : %d\n", division(n, d, d, &rem));
    printf("Remainder: %d\n", rem);

    return 0;
}

चूंकि बिट वार ऑपरेशंस बिट्स पर काम करते हैं जो या तो 0 या 1 हैं, प्रत्येक बिट 2 की शक्ति का प्रतिनिधित्व करता है, इसलिए यदि मेरे पास बिट्स हैं

1010

वह मान 10 है।

प्रत्येक बिट दो की शक्ति है, इसलिए यदि हम बिट्स को दाईं ओर स्थानांतरित करते हैं, तो हम 2 से विभाजित होते हैं

1010 -> 0101

0101 5 है

इसलिए, सामान्य रूप से यदि आप 2 की कुछ शक्तियों से विभाजित करना चाहते हैं, तो आपको उस मूल्य को प्राप्त करने के लिए दो को बढ़ाए गए एक्सपोनेंट द्वारा सही स्थानांतरित करने की आवश्यकता है

इसलिए उदाहरण के लिए, 16 तक विभाजित करने के लिए, आप 2 ^^ 4 = 16 के रूप में 4 से स्थानांतरित करेंगे।