Implement division with bit-wise operator

bit-manipulation bit
TimeToCodeTheRoad picture TimeToCodeTheRoad · Mar 12, 2011 · Viewed 99.9k times · Source

How can I implement division using bit-wise operators (not just division by powers of 2)?

Describe it in detail.

Answer

Oliver Charlesworth picture Oliver Charlesworth · Mar 12, 2011

The standard way to do division is by implementing binary long-division. This involves subtraction, so as long as you don't discount this as not a bit-wise operation, then this is what you should do. (Note that you can of course implement subtraction, very tediously, using bitwise logical operations.)

In essence, if you're doing Q = N/D:

  1. Align the most-significant ones of N and D.
  2. Compute t = (N - D);.
  3. If (t >= 0), then set the least significant bit of Q to 1, and set N = t.
  4. Left-shift N by 1.
  5. Left-shift Q by 1.
  6. Go to step 2.

Loop for as many output bits (including fractional) as you require, then apply a final shift to undo what you did in Step 1.

Related questions

Bitwise operator for simply flipping all bits in an integer?

I have to flip all bits in a binary representation of an integer. Given: 10101 The output should be 01010 What is the bitwise operator to accomplish this when used with an integer? For example, if I were writing a method like …

Read More
How to extract specific bits from a number in C?

I need to extract specific part (no of bits) of a short data type in C. For Example I have a binary of 52504 as 11001101000 11000 and I want First 6 ( FROM LSB --> MSB i.e 011000 decimal 24) bits and rest of 10 …

Read More
Check value of least significant bit (LSB) and most significant bit (MSB) in C/C++

I need to check the value of the least significant bit (LSB) and most significant bit (MSB) of an integer in C/C++. How would I do this?

Read More