C++ Tutorials - Absolute n00b spoonfeed

Here is a project that requires you to think a little bit.


It's not so much the code rather then the way you do it.
The goal is to come up with a program that does the following:


User enters a number:
Computer prints out Even or Odd:


Sounds simple enough although there is no built in function that tells you if a number is even or odd.


HINT:

Use the mod Operator. '%'


:):):):):)

Good luck

Here is my go :

Code: Select all

#include <iostream>
using namespace std;

int main (  )
{
   int num;
   cout << "Please enter a number : ";
   cin >> num;

   if ( num % 2 == 0 )
   {
      cout << "Number is even!" << endl;
   }

   else
   {
      cout << "Number is odd!" << endl;
   }

   main (  );
   
   return 0;
}


This is where knowledge of binary and the binary operators comes in handy too, e.g.

Code: Select all

#include <iostream>
using namespace std;
int main()
{
    int iNum;
    cout << "Enter a number :";
    cin >> iNum;

    cout << "Number is ";
    if ( iNum & 1 )
    {
        cout << "odd" << endl;
    }
    else
    {
        cout << "even" << endl;
    }
}


Cake for whoever can explain why this works.

Took me a while to understand your code... I'm still not entirely sure how that works, because doesn't iNum have to be 0 to create a false expression ?

I do like asib's code better. But I guess gooberius has it too. Good job guys keep up the good work.

asib wrote:Took me a while to understand your code... I'm still not entirely sure how that works, because doesn't iNum have to be 0 to create a false expression ?

No, you're thinking of the logical and operator (&&). This is a bitwise and (&). So the result of the expression is a value that has bits set where there are bits set in both left and right subexpressions. If the number is even then the lowest bit won't ever be set (because that bit, if you think back to how binary works, represents the value 1), so 0 & 1 = 0. If the number is odd then the lowest bit will be set, so 1 & 1 = 1. Once the bitwise and is done then the result is treated as a boolean, so anything zero will be false and anything non-zero is treated as true.

Hey Goober. This theory is extremely complicated and this is a forum for begginers so take it easy. Not that your code doesn't work. It is actually very good. But you should probably simlify things when you can.


Good job though, That is pretty cool.

the day ill make a tutorial about bit-playing, ill prolly have a long white beard

[advanced]
but the idea behind it is interesting gooberius. im not so good with bits myself but the part about the right-most bit being the deciding odd-or-even factor definitely makes sense.
[/advanced]

Hi all. I wrote this to expand on what I did with the even/odd problem and hopefully to spread the word about bits, bitwise operators and binary arithmetic. I'll come clean, I'm not a n00b, I've been programming for about 26 years (since I was a little kid with my ZX Spectrum) and for the last 10 of those years I've been a professional game developer. I did come here, however, to try and help out any newbies specifically with parts of programming that I think are becoming lost arts. Bit operations is one of those areas, sadly, which is a shame because you can do a lot of really cool stuff. Perhaps more suited to systems level programming, which I consider game development, but definitely useful stuff to know.

Enough with the pointless rambling. On to the quick lecture!

Bits

The most fundamental item of storage in a binary computer is a single bit. A bit can be in one of two states at any one time, off or on. Off and on are often also referred to as 0 and 1 respectively.

Logic gates

You can perform basic operations on bits by using logic gates. A logic gate is a thing that takes a number of inputs, performs some operation on those inputs and provides an output (which could be used as an input to other logic gates, to switch a light or motor on, or whatever you choose to do with the output). All non-trivial, digital hardware contains millions of logic gates, where each logic gate is constructed from transistors, all arranged in specific configurations, to perform the required tasks. It's a fairly huge leap to go from a single logic gate to a complete CPU, so we'll take things slowly .

For our purposes we are going to concern ourselves with 4 logic gates. There are others, but they are variations on combinations of these basic four, so we'll ignore them for now. So, our 4 logic gates are AND, OR, NOT and XOR (I'll use the convention that logic gates are all caps to avoid confusing "AND" with "and", etc).

One thing that makes digital logic easier to learn is the concept of a truth table. A truth table is a way of describing how a system works by examining its inputs and outputs, so we'll introduce each gate, show its symbol, explain in English what it does and present a truth table that should help your understanding.

-- AND --

The AND gate requires both of its inputs to be 1 for its output to be 1. In all other states its output will be zero.

Truth table for AND
A | B || C
0 | 0 || 0
1 | 0 || 0
0 | 1 || 0
1 | 1 || 1

The truth table here is saying, for each row, what the inputs (A, B) are and what the output (C) is for those inputs.

-- OR --

The OR gate requires either of its inputs to be 1 for its output to be 1. The output is also 1 in the case where both inputs are 1.

A | B || C
0 | 0 || 0
1 | 0 || 1
0 | 1 || 1
1 | 1 || 1

-- NOT --

The NOT gate inverts the input, outputting a 1 when a 0 is input and vice versa. Unlike the other gates described, NOT gates have one input.

A || C
0 || 1
1 || 0

-- XOR --

The XOR gate is related to the OR gate. It too requires either of its inputs to be 1 for the output to be 1, but in the case where both inputs are 1 its output is 0.

A | B || C
0 | 0 || 0
1 | 0 || 1
0 | 1 || 1
1 | 1 || 0

Binary arithmetic and powers of two

There are 10 types of people in the world; those who understand binary and those who don't. Taking a slight detour from logic gates, we'll look at simple binary arithmetic, then we'll come back to the logic gates and do some math with them (no, really! ). Going back to bits and how they can be off or on, that's not a huge amount of use on its own, but it becomes a lot more useful when you group a bunch of bits together. It's now standard practice to call a group of 8 bits a byte, for example. The older generation of programmers and electronic engineers call a group of 4 bits a nibble or nybble. We won't get too far ahead of ourselves, so we'll look at a group of 3 bits (which, as far as I know, doesn't have any particular name).

So, what can we do with our two bits? Well, each bit can be independantly switched off or on, so I'll write out the various combinations first

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Ok, we have 8 different combinations. It's still not massively useful in itself, so we'll assign decimal values to each bit. We'll call the rightmost bit, bit zero. The next left bit will be bit one. The leftmost bit will be bit two. If we had more bits then they'd be bits 3, 4, 5, etc. Starting from the rightmost bit and working left, we'll assign each bit a value that is equal to 2^bitnumber (remember n^0 = 1). e.g.

bit number 2 1 0
value 4 2 1

So, bit zero is "worth" one, bit one is "worth" two and bit two is "worth" four. Now things start to get more useful, because we now have the ability to count in binary. All we need to do is see which bits are set to 1 and we add up the decimal values of all the set bits. For example, given the three bits 1 0 1, we know that the rightmost bit is worth 1, the leftmost bit is worth 4 and the middle bit is off, so we don't count it. Adding those values up gives us the answer, 5. So binary 101 is decimal 5. You should now be able to go through the binary table I drew up earlier and figure out the decimal values for each binary value. I'll do that as an example here

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

So you can see that with 3 bits we can represent the decimal numbers zero to seven. As you add more bits on the left the range of values you can represent increases. More specifically, given n bits you can represent values from 0 to 2^n-1. So, a byte can represent values between 0 and 255, and so on. Negative numbers are possible, but a trickier proposition; if you're interested and want some homework then look into "two's complement" representation.

So now you know how integer values are stored in the computer. Even though you declare an "int" in C/C++, it's all just a bunch of bits.

More complex logic systems

As I said a little earlier, logic gates can be connected together to construct more complex systems. One of these complex systems is called an adder, and it does as the name suggests, it adds. Specifically it adds two binary numbers. Rather than me badly describe it here it's probably better if you refer to this [http://en.wikipedia.org/wiki/Adder_%28electronics%29] Wikipedia page (if you're interested). You don't really need to fully understand this, but you do need to be convinced that numbers held in your computer are held in a binary representation.

Ok, so now we know that numbers are held in binary we can start to do some funky things with the bit operations in C/C++. If you refer to my solution to the even/odd problem you can see that the line that did the work was

if ( iNum & 1 )

so what's this line doing? Imagine iNum is actually a 3 bit value rather than 32 bit for a second. What I'm doing here is asking the computer to do a bitwise AND between the value in iNum and the binary value 001 (because decimal 1 is binary 001). This has the effect of returning a value which only has bits set where there were bits set in both of the input values. Because one of the input values has just the zero'th bit set (1) then it stands to reason that the only case where the result of this could be anything other than zero is where iNum has its zero'th bit set too. If you refer back to the binary arithmetic we did earlier you'll see that the only odd bit is the zero'th bit - all other bits have even values, and so we have an easy way of determining if a number is even or odd.

But the fun doesn't end there. We actually have a bunch of other useful bit operators we can do stuff with. Cast your mind back to the logic gates from earlier. What would we do if we wanted to OR two values together? Well, C++ has a bitwise OR operator "|". So, what happens when we do, for example, (iNum | 1)? Well, we'll get a result which is whatever is in iNum, but with the zero'th bit set. So you can take any value and make it an odd number equal to or one greater than the original value. C++ also has operators for XOR (^) and NOT (~), should you want to use them.

Two other operators I'd like to cover are the bit shifting operators. Unfortunately the stream in/out operators use the same symbols as the bit shift operators, << and >>, but they act completely differently. Lets say you do the following,

int x = 3;
x = x << 1;

What you are saying here is that you want the bits in x to be shifted left by one place. Likewise you can do

int x = 8;
x = x >> 1;

And here the bits will be shifted to the right by one place. So what happens to the bits? Let's look at the first example,

int x = 3;
x = x << 1;

I'll write the binary values as 4 digits, so 3 would be 0011. If we move each bit in the value to the left by one place we get the binary value 0110. As we shift bits across we shift in unset bits. So, for the second example we start with 1000, shift it right one place and end up with 0100.

How is that useful? Well, it's good for a bunch of things, but one thing to notice is that what you are doing is replacing each set bit (2^bit) by a new value (2^(bit+num_shift_bits)). If you're still none the wiser then don't worry, it's not particularly obvious, but basically you are multiplying and dividing the values by powers of two. Shifting left is equivalent to multiplying by a power of two, shifting right is equivalent to dividing by a power of two. The actual value you are multiplying or dividing by is a function of the number of bits that you are shifting, 2^num_bits. So shifting left by one bit is a multiply by two. Shifting right by 3 bits (2^3 = 8 ) is dividing the value by 8.

I'll wrap things up there I think. There's more to learn, as I said, negative numbers are just one area to look into, but I hope this has been useful and not too boring for you. Comments are more than welcome and I'll try to answer any questions about this stuff if anyone needs further help.



[edit] Apologies for the ridiculous length of this post!

totally awesome!... did anyone else understand? i think i did!

I somewhat understood this.

Great job. Gooby.

not to offend gooberius or anything, but i'd still tag the whole subject as [advanced]

Wow, very interesting. I had a question, Gooberius: Using the bit shift operators, when you shift it to the right, is that the same thing as finding the square root of a number? Or would is be the same as having negative exponents, like 5^-2, which would be 1/25.

I have planning to make a program to solve quadratic formulas, yet i'm still figuring out the <cmath> uses, which is confusing me....
Do you think i could use this to find square roots, and thus solve my problem (there are square roots in the quadratic equation)

No, shifting left is effectively multiplying by 2^number_of_places_shifted. Similarly, shifting right is dividing by 2^number_of_places_shifted.

While you could do a square root in integer*, it's likely you'd lose too much precision (in this case, everything after the decimal point), so your best bet would be to use floating point values instead. There is a square root function already provided for you, defined in <cmath>, e.g

Code: Select all

#include <cmath>
#include <iostream>

using namespace std;

int main( )
{

    float fVal = 9.0f;
    float fSquareRoot = sqrt( fVal );

    cout << "The square root of " << fVal << " is " << fSquareRoot << endl;
}


* I'm specifically referring to integer here. You could do your maths in fixed point (which uses integer operations) and it'd work just fine, but that's definitely getting into the realm of "more advanced than is appropriate for this thread". Just use floats and let the computer do the hard work, that's what they are there for

Someone should post a thread on all the basic libraries.
And there functions. I'm lazy so I can't do it.

But, someone really should. I'm sure that a few people would appreciate it.



Maybe I will. If I find time in my hectic busy social life with all my really cool friends.


Just a suggestion.