Podział implementacji z operatorem bitowym
Jak zaimplementować dzielenie za pomocą operatorów bitowych (nie tylko dzielenie przez potęgi 2)?
Opisz to szczegółowo.
11 answers
Standardowym sposobem dzielenia jest implementacja binarnego długiego dzielenia. Wiąże się to z odejmowaniem, więc o ile nie dyskontujesz tego jako Niezbyt mądrej operacji, to właśnie powinieneś to zrobić. (Zauważ, że możesz oczywiście zaimplementować odejmowanie, bardzo żmudnie, używając bitowych operacji logicznych.)
W istocie, jeśli robisz Q = N/D
:
- Wyrównaj najważniejsze z
N
iD
. - Oblicz
t = (N - D);
. - If
(t >= 0)
, then set the least significant bit ofQ
to 1, and setN = t
. - Left-shift
N
o 1. - Left-shift
Q
o 1. - przejdź do kroku 2.
Wykonaj pętlę dla dowolnej liczby bitów wyjściowych (w tym ułamkowych), a następnie zastosuj ostatnią zmianę, aby cofnąć to, co zrobiłeś w Kroku 1.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-06-17 11:25:44
Podział dwóch liczb za pomocą operatorów bitowych.
#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();
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-09 12:36:04
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();
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-08-08 16:48:10
To rozwiązanie działa idealnie.
#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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-09 12:36:34
Zakładam, że omawiamy podział liczb całkowitych.
Weź pod uwagę, że mam dwie liczby 1502 i 30 i chciałem obliczyć 1502/30. Tak to robimy:
Najpierw zestawiamy 30 z 1501 w jego najbardziej znaczącej liczbie; 30 staje się 3000. I porównaj 1501 z 3000, 1501 zawiera 0 z 3000. Następnie porównujemy 1501 z 300, zawiera 5 z 300, a następnie porównujemy (1501-5 * 300) z 30. W końcu w wyniku tego podziału otrzymaliśmy 5*(10^1) = 50.
/ Align = "left" / 1501 i 30 na cyfry binarne. Następnie zamiast mnożyć 30 z (10^x), aby wyrównać z 1501, mnożemy (30) W 2 bazie z 2^n, aby wyrównać. I 2^n można przekształcić w lewo przesunięcie n pozycji.Oto 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;
}
Nie testowałem tego, ale masz pomysł.Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-09 12:41:29
Poniższa metoda jest implementacją podziału binarnego, biorąc pod uwagę, że obie liczby są dodatnie. Jeśli odejmowanie jest problemem, możemy to zaimplementować również za pomocą operatorów binarnych.
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);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-09 12:43:09
Wszystkie te rozwiązania są zbyt długie. Podstawowym założeniem jest zapis ilorazu (np. 5=101) jako 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(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 + ") ";
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-09 12:43:46
Dla liczb całkowitych:
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);
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-09 12:44:40
Ze zwykłymi zastrzeżeniami dotyczącymi zachowania C z przesunięciami, powinno to działać dla niepodpisanych ilości niezależnie od natywnego rozmiaru 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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-10-11 02:55:13
Podział implementacji bez operatora podziału: Będziesz musiał uwzględnić odejmowanie. Ale wtedy jest tak, jak robisz to ręcznie(tylko w oparciu o 2). Załączony Kod zapewnia krótką funkcję, która robi dokładnie to.
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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-11-09 13:09:24
Ponieważ operacje bitowe działają na bitach, które są 0 LUB 1, każdy bit reprezentuje moc 2, więc jeśli mam bity
1010
Ta wartość to 10.
Każdy bit jest potęgą dwóch, więc jeśli przesuniemy bity w prawo, dzielimy przez 2
1010 --> 0101
0101 jest 5
Tak więc, ogólnie rzecz biorąc, jeśli chcesz podzielić przez jakąś potęgę 2, musisz przesunąć w prawo o wykładnik, do którego podnosisz dwa, aby uzyskać tę wartość
Więc na przykład, aby podzielić przez 16, przesuniesz o 4, jak 2^^4 = 16.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-03-12 19:33:43