按位运算符实现分割
我怎样才能使用按位运算符来实现分割（不仅仅是2的幂）？
详细描述。
做分工的标准方法是实行二元分法。 这涉及到减法，所以只要你不打算把它当作一个按位操作，那么这就是你应该做的。 （注意，你当然可以使用按位逻辑操作非常枯燥地执行减法。）
实质上，如果你在做Q = N/D ：
- alignment
N和D最重要的那些。 - 计算
t = (N - D);。 - 如果
(t >= 0)，则将Q的最低有效位设置为1，并设置N = t。 - 左移
N1。 - 左移
Q1。 - 转到第2步。
根据需要循环输出比特数（包括小数），然后应用最后一次移位来撤销步骤1中所做的操作。
使用按位运算符来划分两个数字。
#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", ÷nd); 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(); }
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", ÷nd); 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(); } }
这个解决scheme完美。
#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; }
我假设我们正在讨论整数的划分。
考虑到我得到了两个数字1502和30，我想计算1502/30。 这是我们如何做到这一点：
首先，我们将30与1501相提并论， 30变成3000.然后把1501和3000比较，1501中包含3000个。然后我们比较1501和300，它包含300中的5个，然后比较（1501-5 * 300）和30.最后我们得到了5 * 10 ^ 1）= 50作为这个划分的结果。
现在将1501和30转换成二进制数字。 然后用（10 ^ x）乘以30来使它与1501alignment，而不是用2 ^ n乘以（2）中的（30）来alignment。 而2 ^ n可以转换为左移n位置。
这里是代码：
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; }
没有testing，但你明白了。
下面的方法是考虑到两个数字都是正数的情况下二进制分割的实现。 如果减法是一个问题，我们可以使用二元运算符来实现。
码
-(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); }
所有这些解决scheme都太长了。 其基本思想是将商（例如5 = 101）写为100 + 00 + 1 = 101。
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(aq, b); return new Point(c + rx, ry); } 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 (bx - x != 0) { return x - bx; } else { return y - by; } } @Override public String toString() { return " (" + x + " " + y + ") "; } }
对于整数：
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); } }
通常有关C的行为与变化的警告，这应该适用于无符号数量，无论本地大小的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; }
在没有divison运算符的情况下实现分割：您将需要包含减法运算。 但是，就像你手工做的一样（只有2）。 附加的代码提供了一个简短的function，就是这个function。
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 // // ie: 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或1的比特上工作，每个比特代表2的幂，所以如果我有比特
1010
那个值是10。
每一位都是二的幂，所以如果我们把位移到右边，我们除以2
1010 – > 0101
0101是5
所以，一般来说，如果你想用2的幂来除，你需要按照你提出的2的指数向右移动来获得这个值
例如，除以16，你会移动4，因为2 ^^ 4 = 16。
