2

I was looking at the binary integer division with remainder section in Wikipedia and was wondering how would I translate this into another language like C for example? 

if D == 0 then error(DivisionByZeroException) end
Q := 0                 -- initialize quotient and remainder to zero
R := 0                     
for i = n-1...0 do     -- where n is number of bits in N
  R := R << 1          -- left-shift R by 1 bit
  R(0) := N(i)         -- set the least-significant bit of R equal to bit i of the numerator
  if R >= D then
    R := R - D
    Q(i) := 1
  end
end

I know how to translate the majority of it and do the bit shifting, but how would I do something like R(0) = N(i) or Q(i) = 1 when they are integers and not a function or a function pointer? Sorry for the basic question, the little section just got me interested.

Nisse Engström
  • 4,738
  • 23
  • 27
  • 42
user27546
  • 23
  • 3
  • 1
    masking and using bitwise operations. 0010 | 1000 = 1010. You just set one of the bits. Look into that for further explanations: http://www.cprogramming.com/tutorial/bitwise_operators.html and one from here: http://stackoverflow.com/questions/10493411/what-is-masking – zubergu Feb 27 '15 at 23:25
  • 1
    possible duplicate of [How do you set, clear and toggle a single bit in C/C++?](http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c-c) – John Bupit Feb 27 '15 at 23:31

1 Answers1

1

Here is how you do it.

// R(0) := N(i)
R = (R & ~0x01) | ((N >> i) & 0x01);

The first part clears the 0 bit of r, then you OR it with the i'th bit of N, which you've shifted down into the 0 bit place. You have to clear the bit first in case N(i) == 0.

// Q(i) = 1
Q |= 0x01 << i;

In this case, 0x01 is a single bit, then you shift it into place. Since you are setting the bit regardless of what it was before, the OR operation will work.

To give some general binary operations:

If you want a single bit of information X(n):

(X >> n) & 0x01;

If you want to set a bit to 1 is above.

If you want to clear a bit to 0, X(n) = 0:

X &= ~(0x01 << n);

If you want to toggle a bit, X(n) = !X(n):

X ^= (0x01 << n);

If you want to assign a binary value to a bit, X(n) = y:

X = (X & ~(0x01 << n)) | (y << n);  // Assumes y = 0 or 1.
caveman
  • 1,755
  • 1
  • 14
  • 19
  • You don't even need to clear the bit in the first line, since `R` was shifted left in the line before. – Stefano Sanfilippo Feb 27 '15 at 23:28
  • 1
    True. But I would have to add context to describe that. So I just did the operation in isolation. I made a simplifying example to make that detail there, because it is often missed by beginners. – caveman Feb 27 '15 at 23:32