11 Soru: Bit-bilge operatör ile bölme uygulama

tarafından oluşturulan soru Sat, Aug 8, 2015 12:00 AM

Bit bilge işleçleri kullanarak bölmeyi nasıl uygulayabilirim (sadece 2'nin güçleriyle bölme değil)?

Ayrıntılı olarak açıklayın.

    
47
  1. Bkz. Yalnızca bit kaydırma ve ekleme kullanarak nasıl çarpabilir ve bölebilirim? Kompakt, verimli, özyinelemeli olmayan bir C uygulaması için. (Ve buna benzer bir x86-asm uygulaması.)
    2018-06-20 18: 24: 02Z
  2. Birisi size bu soruyu bir röportajda sorarsa, "sor, günlük yaptığınız bir şey mi, bölmeyi uygula" mı?
    2019-04-23 05: 07: 26Z
11 Yanıtlar                              11                         

Bölünmenin standart yolu, ikili uzun bölme uygulamaktır. Bu, çıkarma işlemini içerir, çünkü bunu biraz akıllıca bir işlem olarak indirim yapmazsanız, o zaman yapmanız gereken budur. (Elbette, bitsel mantıksal işlemler kullanarak çok sıkıcı bir şekilde çıkarma işlemi gerçekleştirebileceğinizi unutmayın.)

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

  1. N ve D’un en önemli olanlarını hizalayın.
  2. t = (N - D); Hesapla.
  3. (t >= 0) ise, Q’un en az anlamlı bitini 1’e ayarlayın ve N = t’u ayarlayın.
  4. N x 1 sola kaydırma.
  5. Q x 1 sola kaydırma.
  6. 2. adıma gidin.

İstediğiniz kadar çıktı bitini (kesirli dahil) için döngüleyin, ardından 1. Adımda yaptığınız işlemi geri almak için son bir vardiya uygulayın.

    
55
2014-06-17 11: 25: 44Z
  1. N ve D'nin en belirgin olanlarını hizalayarak ne demek istiyorsunuz ve bunu kodda mı yapıyoruz?
    2011-03-13 04: 56: 03Z
  2. @ Zaman: Örneğin N = 9 ve D = 3 ise, N = 1001, D = 11 olur. Bu yüzden yapılacak ilk şey D ile 2 arasında bir kaydırma yapmaktır, böylece baştaki biri N ile eşleşir, yani D = 1100 ile çalışırsınız.
    2011-03-13 10: 03: 52Z
  3. @ Foli: t < 0. N = 1001 ve D = 11 için, N ve D'yi hizalarsam, N 1001'dir, ancak D 1100'dür. N-D negatif. Fakat sizin algorthim o zaman ne yapacağınızı söylemez. Tam bir örnek verebilir misiniz
    2011-03-14 05: 52: 06Z
  4. @ Programcı: Ah, 3. adımda örtük olduğunu varsaydım; t> gt = 0 ise, lsb'yi Q olarak ayarlayın ve N'yi değiştirin, aksi takdirde ikisini de yapmayın. Eğer daha önce elle uzun bölümler kurduysanız, bu algoritmanın aşina olması gerekir (1001'i 0011'i elle bölmeyi deneyin!).
    2011-03-14 08: 27: 27Z
  5. Ben bu algo için küçük bir sorun olduğunu düşünüyorum, bu da 3. adımdan önce 5. adımı yapmamız gerektiğidir. bir kez döngü gerekir. 3. adımdan sonra, Q = 1 ve açıkça 5. adımdan sonra yapmamalıyız, aksi takdirde Q 10 olur.
    2012-09-11 01: 03: 33Z

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();
}
    
9
2015-09-09 12: 36: 04Z
  1. nereden divisor alıyorsunuz?
    2014-03-29 14: 11: 17Z
  2. bu, scanf("%d", &divisor);'dan gelen kullanıcı girişidir
    2016-04-17 00: 38: 49Z
  3. Yalnızca, normal bir süre (dolandırıcılığı yerine < < < 1 ile) tempdivisor < < 1 ile) yaparsanız doğru şekilde bölünür Bölüm bölümü bunu mahveder.
    2017-03-07 21: 10: 14Z
 
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
2015-08-08 16: 48: 10Z
  1. Test ettim. Negatif bölünmeyi kaldırabilir
    2012-08-29 08: 29: 58Z

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

 
#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
2015-09-09 12: 36: 34Z

Tam sayıların bölünmesini tartıştığımızı farz ediyorum.

İki tane 1502 ve 30 numara aldığımı ve 1502/30 hesaplamak istediğimi düşünün. Bunu nasıl yapıyoruz:

Öncelikle 30'u 1501 ile en belirgin şekilde hizalıyoruz; 30, 3000 olur. Ve 1501'i 3000 ile karşılaştırır, 1501, 3000'in 0'ını içerir. Sonra 1501'i 300'le karşılaştırırız, 300'ünü içerir, sonra (1501-5 * 300) 'ı 30'la karşılaştırırız. 10 ^ 1) = Bu bölümün sonucu olarak 50.

Şimdi hem 1501 hem de 30'u ikili sayılara dönüştürün. Daha sonra 1501 ile hizalamak için 30'u (10 ^ x) ile çarpmak yerine, hizalamak için 2 bazda 2 ^ n ile çarpıyoruz (30). Ve 2 ^ n, sola kayma n pozisyonlarına 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 etmediniz, ancak fikri anladınız.

    
2
2015-09-09 12: 41: 29Z

Bölüm operatörü olmadan bölüm oluşturma: Çıkarmayı eklemeniz gerekecek. Fakat o zaman aynen elle yaptınız gibi (sadece 2'nin temelinde). Ekteki 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;
}
    
1
2017-11-09 13: 09: 24Z

Aşağıdaki yöntem, her iki sayının da pozitif olduğunu düşünerek ikili bölünmenin uygulanmasıdır. Çıkarma bir endişe ise, ikili operatörleri kullanarak da bunu yapabiliriz.

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
2015-09-09 12: 43: 09Z

Tam sayılar 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
2015-09-09 12: 44: 40Z
  1. bu taşma ile ilgilenmez. Temettüm, tamsayı için 32 bit varsayarsak -2 ^ 31 ise?
    2016-09-29 16: 24: 41Z

Her zamanki gibi C'nin kaymalarla olan davranışına ilişkin uyarılarla, bu, bir int'nin yerel boyutundan bağımsız olarak, imzasız miktarlarda çalışması gerekir.  

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: 13Z

Tüm bu çözümler çok uzun. Temel düşünce 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 + ") ";
    }
}
    
- 1
2015-09-09 12: 43: 46Z

Bit bilge işlemler 0 veya 1 olan bitler üzerinde çalıştığından, her bit 2'nin gücünü gösterir, bu yüzden eğer bitlerim varsa

1010

bu değer 10'dur.

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

1010 - > 0101

0101, 5'dir

bu nedenle, genel olarak 2 gücüne bölmek istiyorsanız, bu değeri elde etmek için ikie yükselteceğiniz üste doğru kaydırmanız gerekir.

bu nedenle, örneğin 16'ya bölmek için 4, 2 ^^ 4 = 16 olarak kaydırılır.

    
- 2
2011-03-12 19: 33: 43Z
  1. OP’nin sadece 2’lik güçlere bölünmekle ilgilendiğini sanmıyorum.
    2011-03-12 19: 38: 31Z
  2. Oli haklı! 2’nin güçleri olmayan sayılarla bölmek istiyorum
    2011-03-13 04: 56: 44Z
kaynak yerleştirildi İşte