Soru Bit-bilge operatörüyle bölümü uygulama


Bit-bilge operatörleri kullanarak bölünmeyi nasıl kurabilirim (sadece 2'nin yetkileri ile değil)?

Bunu ayrıntılı olarak açıklayın.


43
2018-03-12 19:29


Menşei


Görmek Sadece bit kaydırma ve ekleme kullanarak nasıl çoğalabilir ve bölebilirim? Kompakt, verimli, tekrarlamalı bir C uygulaması için. (Ve benzer bir x86-asm uygulaması.) - Peter Cordes


Cevaplar:


Bölmeyi yapmanın standart yolu, ikili uzun bölünmeyi uygulamaktır. Bu, çıkarma işlemini içerir, bu yüzden bunu bir bitlik işlem olarak indirmediğiniz sürece, yapmanız gereken şey budur. (Tabii ki çıkarma işlemini, çok yorucu bir şekilde, bitsel mantıksal işlemleri kullanarak gerçekleştirebileceğinizi unutmayın.)

Özünde, eğer yapıyorsan Q = N/D:

  1. En önemli olanları hizalayın N ve D.
  2. hesaplamak t = (N - D);.
  3. Eğer (t >= 0)sonra en az anlamlı biti ayarlayınız. Q 1 ve set N = t.
  4. Sol shift N 1 tarafından.
  5. Sol shift Q 1 tarafından.
  6. 2. adıma geçin.

Gereksinim duyduğunuz kadar çok sayıda çıktı parçası (kesirli dahil) için döngü yapın ve Adım 1'de yaptığınız işlemi geri almak için son bir geçiş yapın.


52
2018-03-12 19:32



N ve D'nin en önemli olanlarını hizalayarak neyi kastediyorsunuz ve bunu kodda yapıyoruz. - TimeToCodeTheRoad
@ Zaman: Örneğin, N = 9 ve D = 3 ise, N = 1001, D = 11 olur. Öyleyse ilk yapılacak şey, D'nin 2'ye kaymasıdır, böylece öncü olan N'ninkiyle eşleşir, yani D = 1100 ile çalışırsınız. - Oliver Charlesworth
@Foli: Eğer t <0. Eğer N = 1001 ve D = 11 için, N ve D'yi hizalarsam, o zaman N 1001'dir, ancak D 1100'dür. N-D negatiftir. Ama senin algorthim o zaman ne yapacağını söylemiyor. Tam bir örnek verebilir misiniz - Programmer
@Programmer: Oh, 3. adımda üstü kapalı olduğunu varsaydım; t> = 0 ise, Q'nun lsb'sini ayarlayın ve N'yi değiştirin, aksi halde yapma. Eğer el ile uzun bir bölünme yaptıysanız, bu algoritma aşina olmalı (1001'i 0011'e el ile bölmeyi deneyin!). - Oliver Charlesworth
Sanırım bu algoda ufak bir sorun var, bu da adım 3'ten önce 5. adımı yapmamız gerektiğidir. N = 1 ve D = 1 olsun, sadece bir kez döngü yapmamız gerekiyor. 3. adımdan sonra, Q = 1 ve açıkçası bundan sonra 5. adımı yapmamalıyız, aksi takdirde Q 10 olur. - xvatar


Bitsel operatörleri kullanarak iki sayının bölünmesi.

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

7
2017-08-05 19:16



nereden aldın divisor dan? - kapad
gelen kullanıcı girişi scanf("%d", &divisor); - Dorian
Sadece normal bir süre (tempdivisor << 1 ile) do-while yerine doğru şekilde böler. Bölüm parçası bunu vidalar. - Patrick Duncan


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

5
2017-08-29 08:28



Ben test ettim. olumsuz bölünmeyi kaldırabilir - Jack Liu


Bu çözüm mükemmel çalışır.

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

3
2018-02-16 09:39





Tamsayıların bölünmesini tartıştığımızı varsayıyorum.

İki sayı 1502 ve 30 aldığımı ve 1502/30 değerini hesaplamak istediğimi düşünün. Bunu böyle yapıyoruz:

İlk önce 30'u en anlamlı şekilde 1501 ile hizalarız; 30, 3000 olacak ve 1501'i 3000 ile, 1501'i de 3000'i 0 ile karşılaştırınız. Ardından, 1501'i 300 ile karşılaştırdık, 300'ün 5'ini, sonra 30'u (1501-5 * 300) 30 ile karşılaştırdık. Sonunda 5 tane aldık * ( Bu bölümün sonucu olarak 10 ^ 1) = 50.

Şimdi 1501 ve 30'u ikili basamağa dönüştürün. Daha sonra (10 ^ x) ile çarparak 1501 ile hizalamak yerine, hizalamak için 2 bazda (30) 2 baz ile çarpıyoruz. Ve 2 ^ n, sola kaydırma n konumuna dönüştürülebilir.

İşte kod:

int divide(int a, int b){
    if (b != 0)
        return;

    //To check if a or b are negative.
    bool neg = false;
    if ((a>0 && b<0)||(a<0 && b>0))
        neg = true;

    //Convert to positive
    unsigned int new_a = (a < 0) ? -a : a;
    unsigned int new_b = (b < 0) ? -b : b;

    //Check the largest n such that b >= 2^n, and assign the n to n_pwr
    int n_pwr = 0;
    for (int i = 0; i < 32; i++)
    {
        if (((1 << i) & new_b) != 0)
            n_pwr = i;
    }

    //So that 'a' could only contain 2^(31-n_pwr) many b's,
    //start from here to try the result
    unsigned int res = 0;
    for (int i = 31 - n_pwr; i >= 0; i--){
        if ((new_b << i) <= new_a){
            res += (1 << i);
            new_a -= (new_b << i);
        }
    }

    return neg ? -res : res;
}

Test etmedin, ama fikri anladın.


2
2018-02-19 01:29





Aşağıdaki yöntem, her iki sayı da pozitif göz önüne alındığında ikili bölmenin uygulanmasıdır. Çıkarma bir endişe ise, ikili operatörleri kullanarak da uygulayabiliriz.

kod

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

0
2018-02-11 23:13





Bütün bu çözümler çok uzun. Temel fikir, bölümü (örneğin, 5 = 101) 100 + 00 + 1 = 101 olarak yazmaktır.

public static Point divide(int a, int b) {

    if (a < b)
        return new Point(0,a);
    if (a == b)
        return new Point(1,0);
    int q = b;
    int c = 1;
    while (q<<1 < a) {
        q <<= 1;
        c <<= 1;
    }
    Point r = divide(a-q, b);
    return new Point(c + r.x, r.y);
}


public static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compare(Point b) {
        if (b.x - x != 0) {
            return x - b.x;
        } else {
            return y - b.y;
        }
    }

    @Override
    public String toString() {
        return " (" + x + " " + y + ") ";
    }
}

0
2018-03-14 23:37





Tam sayı için:

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

0
2018-04-11 16:52



Bu taşma işlemez. Ne benim temettü tamsayısı için 32 bit varsayarak -2 ^ 31 olsaydı? - huskywolf


C'nin vardiyalı davranışları hakkında olağan uyarılar ile, bu bir int'nin yerel boyutundan bağımsız olarak imzasız miktarlar için çalışmalıdır.

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

0
2017-10-11 02:55





Bölünme operatörü olmaksızın bölüm uygulamak: Çıkarmayı eklemeniz gerekecek. Ama sonra sadece el ile yaptığınız gibi (sadece 2). Eklenen kod, tam olarak bunu yapan kısa bir işlev sağlar.

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

0
2017-11-09 12:59





Bit bilge işlemleri, 0 veya 1 olan bitlerde çalıştığı için, her bit, 2'lik bir gücü temsil eder;

1010

bu değer 10'dur.

Her bit, iki güçtür, bu yüzden bitleri sağa kaydırırsak, 2'ye bölünür.

1010 -> 0101

0101 5

bu yüzden, genel olarak, eğer 2 gücüyle bölünmek istiyorsanız, o değeri elde etmek için ikiye yükseltdiğiniz üssü sağa kaydırmanız gerekir.

Örneğin, 16'ya bölmek için, 4, 4, 4, 16 olarak değişeceksin.


-2
2018-03-12 19:33



OP'nin sadece 2'nin yetkileriyle bölünmesiyle ilgilendiğini sanmıyorum. - Oliver Charlesworth
Oli haklı! 2'nin güçleri olmayan sayılarla bölmek istiyorum - TimeToCodeTheRoad