Author |
Topic: a/b bitwise (Read 1552 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
a/b bitwise
« on: Mar 25th, 2011, 12:52pm » |
 Quote  Modify
|
Divide two numbers(Given a,b, output a/b) by using only bitwise operations.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: a/b bitwise
« Reply #1 on: Mar 27th, 2011, 3:46pm » |
Quote Modify
|
Hint: Long Division in Binary
However: You'll need to define, at a minimum, subtraction and less-than in terms of bitwise operations.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: a/b bitwise
« Reply #2 on: Mar 27th, 2011, 10:22pm » |
Quote Modify
|
on Mar 27th, 2011, 3:46pm, SMQ wrote:Hint: Long Division in Binary
However: You'll need to define, at a minimum, subtraction and less-than in terms of bitwise operations.
--SMQ |
|
Can you explain long division in binary a bit more?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
sunny816.iitr
Newbie
Gender:
Posts: 2
|
|
Re: a/b bitwise
« Reply #3 on: Jul 9th, 2011, 2:41pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: a/b bitwise
« Reply #4 on: Jul 11th, 2011, 8:20am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: a/b bitwise
« Reply #5 on: Jul 12th, 2011, 1:54pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 12th, 2011, 1:55pm by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: a/b bitwise
« Reply #6 on: Jul 12th, 2011, 10:04pm » |
Quote Modify
|
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);
}
|
| « Last Edit: Jul 12th, 2011, 10:04pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: a/b bitwise
« Reply #7 on: Jul 13th, 2011, 5:41am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 15th, 2011, 9:05am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: a/b bitwise
« Reply #8 on: Jul 15th, 2011, 9:26am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print