Finding the remainder using bitwise operators.

[Nalyk]

I recently picked up a book and am currently in the process of teaching myself how to code in C++. At the end of one each chapter are are exercises that you can do to challenge yourself and I'm having trouble figuring out how to approach one specifically.

The direct quoted text is as follows:

"Write a program that reads an integer value from the keyboard into a variable of type "int", and uses one of the bitwise operators(ie not the % operator) to determine the positive remainder when divided by 8. For example, 29 = (3*8)+5 has a positive remainder of 5 when divided by 8.

I think my main problem stems from that I'm still a little unfamiliar with how binary works. I want to write the code, but I can't seem to figure out how to approach the problem.

i.e. using &, |, ^, ~, >> or <<, how can I find the remainder of something say when divided by 8.

On that same note, the book is simultaneously teaching me to code in native C++ and C++/CLI, would it be easier to use C++/CLI because the << and >> operators are used for data flow in C++.

Thanks in advance,
Nalyk

[Intrexa]

Break it down to binary to easier to see what you need to do.

29 = 0001 1101
8  = 0000 1000
5  = 0000 0101

Looking at it this way, it's easy to see that the 8 bit and everything to the left of it needs to be 0.

[Disch]

Binary is just a base-2 numbering system.

In base 10, you increase digits from 0-9 until you run out of digits, at which point to reset to 0 and increase the next digit:

.. 8, 9, 10, 11, ... 98, 99, 100, ...

In base 2, it's the exact same concept, except the only digits you have are 0 and 1 so you "run out" faster:

0, 1, 10, 11, 100, 101, 110, 111, 1000, ...


Each place has a "weight". In decimal, if you have the number 523, the 5 is in the "hundreds" place, giving it a "weight" of five hundred. The 2 is in the tens place, giving it a weight of 20, and the 3 is in the ones place, giving it a weight of 3. The resulting number is the sum of all their weights:

500 + 20 + 3 = 523


The same concept can be applied to binary. Each digit has a weight of 2^n where n is the bit position. That is:

101

the left-most 1 is in the "fours" place, so it has a weight of 4
the right-most 1 is in the "ones" place, so it has a weight of 1

4 + 1 = 5

Therefore 101 in binary is 5 in decimal.

EDIT: doh, ninja'd

[Nalyk]

Excellent! I knew there was a pattern in binary somewhere, I just couldn't quite figure it out.

So for each bit I have represented as turned on, 100 0101 I can add a power of 2?
64 + 8+1
As long as I count out the digits?

I might be able to figure this one out now. I'll be back for more later though probably!

[Disch]

So for each bit I have represented as turned on, 100 0101 I can add a power of 2?
64 + 8+1
As long as I count out the digits?

You got it. That's right. =)

[Nalyk]

Okay, so I found out what I need to do. But I don't quite understand how it works or why. I need to make a mask using & and save some of the bits, but not all of the bits. The book that I'm reading is a little vague about how to use the 0x0F mask, what it represents and how I can filter out higher or lower order bits.

More to the point, because the user could enter any integer, how do I make sure that I know which bits to keep and which aren't important?

Thanks again, Here's my code if it helps!

//Ch2Exercise2 Fun with remainders


#include <iostream>

using std::cout;
using std::endl;
using std::cin;



int main()
{

int value = 0;

int const divisor = 8;

int remainder = 0;





cout << "\nEnter an integr and I'll divide it by 8 and give you the remainder!"
<<endl;
cin >> value;

remainder = value / divisor;
remainder = remainder & 0x0F;

cout << "\nThe remainder is " <<remainder<< " isn't that awesome?!";

return 0;


}

[Disch]

BTW, & 0xF is incorrect, that would be the remainder of division by 16. & 7 would be the remainder of division by 8.

Remember that each bit position has a weight of 2^n. So what would happen if you shift each bit 1 position to the right:

8 = %1000
4 = %0100
2 = %0010
1 = %0001

As that shows, shifting right effectively divides by 2. So now ask yourself what the significance of the 'x' bits are:

%0001xxx

If all those bits are 0, we have 8 (%1000). If all those bits are 1, we have 15 (%1111).

So what is going to happen if we mask out the 'x' bits?

[Nalyk]

If I mask out the x bits, I won't have an answer, because those should be the bits that I want to keep, so theoretically, assuming my understanding is right, my code should read

remainder = remainder & 15;

so that I keep all of the small order bits that comprise the remainder. However when I do this and run my code, I keep getting back an answer remainder of 3. Which leads me to believe that, because of how I have my statements ordered, that my mask is working, but perhaps the way I have my math working isn't giving me what it is that I want. As 8 goes into 29 only 3 times and it's storing the answer of 3 and then running that value through the mask.

But if I change the code to read like this:

remainder = (value/divisor) & 15; I still get the same answer or 3.

Thanks for walking me through this, it's much appreciated!

[Disch]

If I mask out the x bits, I won't have an answer, because those should be the bits that I want to keep

Yeah sorry I got my terms backwards. I meant remove all bits except the 'x' bits.

so theoretically, assuming my understanding is right, my code should read

remainder = remainder & 15;

15 is %1111, so & 15 will keep the low 4 bits.
If you are dividing by 8, you want & 7, which only keeps the low 3.