C++ for beginners, part 5

Let’s get straight to business.

A wee bit more about binary

So, like I was saying, an 8-bit byte can store 256 values.  Due to negative numbers, the default behaviour is to assume that the type is ‘signed’ (may or may not be negative). Signed values use the leading bit for this (typically, 0 is +, 1 is – ). Since one of the 8 bits indicates the sign, there’s 7 bits left for the number. Which is why 8 bits, when signed, store -127 to 127 instead of 0 to 255 (still have 256 values total).

Note: there’s 3 ways of representing negative numbers with a signed bit. For the 3-bit number 5 (101), here are the signed 4-bit systems:

  1. Sign-magnitude: same binary representation, with leading bit. 0101 = 5 and 1101 = -5. Drawback: 0 occurs twice (0000 and 1000) and calculation is wrong way around. E.g. -5+1 is 1|101 + 1 = 1|110 = -6. Oops.
  2. 1’s complement: negative numbers have 1s/0s flipped. 5 is 0|101, so -5 is 1|010. Why? Then addition/subtraction work the right way around for negative numbers. -5+1 is  1|010+1 which is 1|011, or -4
  3. 2’s complement: same as 1s complement, but after flipping the bits, you add 1. For -5: sign (1|101), flip (1|010), add 1 (1|011). Why? Because then addition/subtraction works for the entire +/- range. Excellent explanation here. Scroll down ’till you see diagrams.

In C++, the type ‘int’ is 4 bytes long, so it can store 256*256*256*256 = 4294967296 values! (If signed, then ±2147483648). But these are integers. Numbers with a decimal point are trickier. This type is called a ‘floating point number’. Floating point means the decimal point can be at various positions. (0.1, 35.83, -9234.122 etc). Floating point numbers have one bit for the sign, several bits for the exponent, and several more bits for the actual numbery part. There’s a simple table here that gives a good overview of ranges of different types in C++.

Essentially, if you have an idea of the range or type of number you’ll be working with, you can declare the type that will make the best use of memory space. Here, since we want to divide two integers and then round down, it seems at first that we at least want float to deal with the decimal point. But! We’re rounding down, which is, as far as C++ is concerned, the same as integer division which ignores the fractional part. E.g. 45/4 = 11.25. Or: 11 with a remainder of 1 (4 fits into 45, 11 times. This makes 44, leaving 1).

The binary dealio will seem clearer with an illustration. First, take regular long division:

Integer division in binary is exactly the same process. For 45 / 4, or 101101 / 100, attend:

So integer division in binary, ignores the remainder. So, for our purposes, where we used ‘floor’ in R to round down, we just do integer division and have it round down in C++ by default.

Finally, back to the functions:

Right. We’ve got this function in R, with some very basic parts:

Pic1

  • dividing upper bound by the first factor, then round down
  • for the range of 1 to that number, we get all multiples of that factor
  • do the same for a different factor
  • get unique values
  • sum them all up

The only things we haven’t done in C++ already are assigning vectors of specific lengths, and using a ‘unique’ function. To keep things tidy, we’ll start from this simple template:Pic2

You assign vector length by using parentheses after the vector name. As mentioned, vector length is found by integer division (bound/factor):

Pic3Remember, when using vectors, have ‘#include <vector>’ at the top of the source code. Also, lines 11 and 12 can be on the same line if you want (though it’s a matter of personal taste).

Pic4 C++ can’t assign ranges of numbers the way R can (in R, 1:5 instantly gives 1 2 3 4 5). So with C++ we’ll use simple for-loops to put ranges of values, into vectors:

Pic5

Caveat time: not entirely sure why yet, but the numbering of vector elements starts at 0. So, a 4-element vector has them referenced as 0, 1, 2 and 3. Which is why we have multn1[i – 1] in the loop. So the first time through the loop (i = 1) we put the value into multn1[0], etc.

‘Appending’ two vectors (multiples of 3 and 5) together: the C++ equivalent is ‘insert’. Since insert is a vector function (check out the list on the left here), it’s called by vector.function, same way we had push_back, begin() and end() in the first function we wrote back in part 2:

Pic6

The arguments you give it are:

  1. At which point of vector 1 you want to start adding vector 2
  2. & 3. The range of the first element of vector 2 and the last element of vector 2 you want to add, like so:

Pic7

‘Multn1’ now contains all the values from both vectors! Now all we want is to find the unique, non-repeated values and use ‘accumulate’ to sum them. But according to the reference page for ‘unique’:

Removes all but the first element from every consecutive group of equivalent elements in the range [first,last).

  • So unique(1 2 2 3 4 5 5 6) gives 1 2 3 4 5 6.
  • But unique( 1 2 2 3 4 3 5 6) gives 1 2 3 4 3 5 6
  • If we sort them into order, we make sure duplicates are consecutive, and ‘unique’ can work accordingly.

This is straightforward. For ‘sort’, you need ‘#include <algorithm>’ at the top of the script (also needed for ‘unique’). Then just apply it to the range:

Pic8

Taking a closer look at ‘unique’:

The function cannot alter the properties of the object containing the range of elements (i.e. it cannot alter the size of an array or a container): The removal is done by replacing the duplicate elements by the next element that is not a duplicate, and signaling the new size of the shortened range by returning an iterator to the element that should be considered its new past-the-end element.

The relative order of the elements not removed is preserved, while the elements between the returned iterator and last are left in a valid but unspecified state.

So what is an iterator in this context? It’s something which indicates or points to an element of interest. In this case, the final unique value. Here’s a brief example using the vector ‘1, 2, 3, 2, 5, 4, 5, 6’:

Pic9

  • Lines 9,10,11: Because you can’t just specify the values of a vector, assign them to an array (a fixed length vector). Then create the vector, and have a for-loop which puts each array element into the corresponding vector element. [If you’re asking ‘why not just put the values into the array and apply the functions to to that?’, it’s because arrays don’t have the same functions available to them as vectors do.]
  • Line 12 prints out our original vector (1,2,3,2,5,4,5,6).
  • Lines 14 and 15 sort this vector and print it. (1,2,2,3,4,5,5,6).
  • Line 17 creates our iterator. Since it is a vector iterator, it is declared as vector<int>::iterator. ‘::’ means ‘belongs to’ or the ‘scope’. So this is specifically saying ‘the kind of iterator that is used within the scope of vectors’. The ‘unique’ function has exactly the same syntax as ‘sort’. Easy.
  • Line 18 prints out the vector rearranged:  (1,2,3,4,5,6,5,6). Note that the 7th element (vector[6]), which is ‘5’, is the first element after the final unique value. This is the ‘past-the-end’ element. From the .end() page:

Because the ranges used by functions of the standard library do not include the element pointed by their closing iterator [.end()], this function is often used in combination with vector::begin [.begin()] to specify a range including all the elements in the container.

  • So our iterator called ‘it’ is pointing to the 7th element. Which is why on line 20, the accumulate function calls the range from ‘.begin()’ to ‘it’, but actually accumulates the values from begin to it-1. Which is the sum of 1:6, or 21.
  • Line 22 sums the range from .begin() to .end(), showing how ‘it’ is working as if it were indicating an element. Which it is.

So, let’s just add the iterator and ‘unique’ to our function (line 26 below), and then finally sum up those values (line 27) and see if it works:

Pic10

It does. Sorted. Next post is the third and final function we wrote for problem 1, which is not so much a function as a very simple equation. The only things it requires are cin and cout. The rest of that post will a) hopefully compare speeds between the same functions in R and C++, and b) put all 3 functions into one little program that lets you choose which method you want to perform.

Advertisements
This entry was posted in C++, Problem 1 and tagged , . Bookmark the permalink.

One Response to C++ for beginners, part 5

  1. Pingback: Problem 2: Fibonacci Cquence | hercles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s