Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
922 views
in Technique[技术] by (71.8m points)

bit manipulation - Implement division with bit-wise operator

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

Describe it in detail.

Question&Answers:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...