wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> a/b bitwise
        
(Message started by: birbal on Mar 25th, 2011, 12:52pm)
Title: a/b bitwise
Post by birbal on Mar 25th, 2011, 12:52pm
Divide two numbers(Given a,b, output a/b) by using only bitwise operations.
Title: Re: a/b bitwise
Post by SMQ on Mar 27th, 2011, 3:46pm
Hint: [hide]Long Division in Binary[/hide]

However: [hide]You'll need to define, at a minimum, subtraction and less-than in terms of bitwise operations.[/hide]

--SMQ
Title: Re: a/b bitwise
Post by birbal on Mar 27th, 2011, 10:22pm

on 03/27/11 at 15:46:21, SMQ wrote:
Hint: [hide]Long Division in Binary[/hide]

However: [hide]You'll need to define, at a minimum, subtraction and less-than in terms of bitwise operations.[/hide]

--SMQ

Can you explain long division in binary a bit more?
Title: Re: a/b bitwise
Post by sunny816.iitr on Jul 9th, 2011, 2:41pm
Long division in Binary :

Every time find highest power of 2 that when multiplied with divisor is less than dividend, subtract it from dividend and continue till dividend is less than divisor

Ex. a = 103 b = 17
17*4 < 103 < 17*8
so highest power of 2 is 4 so q = 4

now a = 103 - 68 = 35, b = 17
17*2 < 35 < 17*4                                          
highest power of 2 is 2 so q = 4+2 = 6

now a = 1 b = 17
a < b.......return
Title: Re: a/b bitwise
Post by SMQ on Jul 11th, 2011, 8:20am
Not terribly efficient, and goes into an infinite loop if division by zero is attempted, but only uses =, ==, !=, ~, &, |, ^, and only the numbers 0 and 1.


#define SIGN_BIT  (~0 & ~(((unsigned)(~0)) >> 1))

/* BASIC OPERATIONS */

// Subtract: compute a + ~b + 1 using ripple-carry adder
int Subtract(int a, int b) {
 int c, ripple, carry, sum;

 ripple = 0;
 do {
   carry = ripple;
   c = 1 | carry << 1;
   ripple = a & ~b | a & c | ~b & c;
 } while (ripple != carry);

 return a ^ ~b ^ c;
}

// Unary Negation
int negative(int i) {
 return Subtract(0, i);
}

// Is-Negative
bool isNegative(int i) {
 return (i & SIGN_BIT) == SIGN_BIT;
}

// Less-Than-Or_Equal
bool lessThanOrEqual(int a, int b) {
 if (a == b) {
   return true;
 } else {
   return isNegative(Subtract(a, b));
 }
}


/* SIGNED BINARY LONG-DIVISION */
int divide(int a, int b) {
 int q, r, s, t, d;

 // set quotient = 0
 q = 0;

 // set remainder = abs(a)
 if (isNegative(a)) {
   r = negative(a);
   s = 1;
 } else {
   r = a;
   s = 0;
 }
 
 // set initial divisor = abs(b)
 if (isNegative(b)) {
   t = negative(b);
   s = s ^ 1;
 } else {
   t = b;
 }

 // set divisor as smallest shift of initial divisor > abs(a)
 d = t;
 while (lessThanOrEqual(d, r)) {
   if (isNegative(d)) break;
   d = d << 1;
 }

 // long division loop: while divisor not initial divisor
 while (d != t) {
   // shift divisor and quotient
   d = d >> 1 & ~SIGN_BIT;
   q = q << 1;
   // subtract divisor if possible
   if (lessThanOrEqual(d, r)) {
      r = Subtract(r, d);
      q = q | 1;
   }
 }
 // although not used, r is now the remainder from the division

 // correct sign of quotient if needed
 if (s == 1) q = negative(q);

 // return final quotient
 return q;
}

--SMQ
Title: Re: a/b bitwise
Post by Grimbal on Jul 12th, 2011, 1:54pm
I've been playing with bitwise operations.  I came up with the following for subtraction, which is probably similar in number of iterations, but has less operations per loop.

int sub(int a, int b){
 while( b ){
   int c = b&a;
   a ^= b;
   b = (b^c)<<1;
 }
 return a;
}

And I was surprised to discover that you can compute addition with:
a+b = ~sub(~a,b)
Not that you need it for division.
Title: Re: a/b bitwise
Post by towr on Jul 12th, 2011, 10:04pm
It shouldn't be that surprising since ~a = -1-a. And of course we can do the reverse, and get subtraction from addition, cutting out another operation from the loop.

int add(int a, int b)
{
 while( b )
 {
   int c = b&a;
   a ^= b;
   b = c << 1;
 }
 return a;
}

int sub(int a, int b)
{
  return ~add(~a, b);
}
Title: Re: a/b bitwise
Post by Grimbal on Jul 13th, 2011, 5:41am
Yep, still simpler.  

My surprise was to discover that after working out an add and a sub, my add ended up being exactly the same as my sub, except that a was reversed at the beginning and at the end.  Previously, I had assumed that going from the one to the other would involve an annoying increment or decrement.
Title: Re: a/b bitwise
Post by Grimbal on Jul 15th, 2011, 9:26am
Due to the lack of any interesting problem around here, I keep playing with this.

You can even remove the extra variable c:  (and yes, sub is simpler again!)

int sub(int a, int b){
 while( b ){
   a ^= b;
   b &= a;
   b <<= 1;
 }
 return a;
}

Now it is pretty much one CPU instruction per line.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board