Shift operator

[Garion]

Chervil was kind enough to post this solution to a problem earlier but there are a few portions of the code I don't fully understand.

I was hoping somebody would explain to me how a few segments of it work.


I'm confused by this line in particular here.

temp |= binary_array[i*6 + j] << (5 - j);



full program here

int main()
{
    int decimal_array[24] = {0};

    int binary_array[144] = // array to convert to 24 dec
    {
       0,0,0,0,0,0,
       0,0,0,0,0,1,
       0,0,0,0,1,0,
       0,0,0,0,1,1,
       0,0,0,1,0,0,
       0,0,0,1,0,1,
       0,0,0,1,1,0,
       0,0,0,1,1,1,
       0,0,1,0,0,0,
       0,0,1,0,0,1,
       0,0,1,0,1,0,
       0,0,1,0,1,1,
       0,0,1,1,0,0,
       0,0,1,1,0,1,
       0,0,1,1,1,0,
       0,0,1,1,1,1,
       0,1,0,0,0,0,
       0,1,0,0,0,1,
       0,1,0,0,1,0,
       0,1,0,0,1,1,
       0,1,0,1,0,0,
       0,1,0,1,0,1,
       0,1,0,1,1,0,
       0,1,0,1,1,1,
    };

    // Binary to decimal
    for (int i=0; i<24; i++)
    {
        int temp = 0;

        for (int j = 0; j<6; j++)
            temp |= binary_array[i*6 + j] << (5 - j);

        decimal_array[i] = temp;
    }


    for (int i=0; i<24; i++)
        printf( "%2d ", decimal_array[i]);
    printf("\n");

    // ------------ Now reverse the process --------------------
    // New Array
    int bin_arr[144];

    // convert decimal to binary.
    for (int i=0; i<24; i++)
    {
        for (int j = 0; j<6; j++)
        {
            int mask = 1 << (5 - j);
            bin_arr[i*6 + j] = ((decimal_array[i] & mask) != 0);
        }
    }

    // output the new binary array
    for (int i=0; i<144; i++)
    {
        if (i % 6 == 0)
            cout << endl;
        else
            cout << ", ";
        cout << bin_arr[i];
    }

    return 0;
}

[booradley60]

Maybe this line of code would be easier to wrap your head around if we could figure out just the binary_array[i*6 + j] part first. For all intents and purposes, i*6 is a way to get to the right "row" of the array. Of course, there aren't really unique rows, since this is a one-dimensional array, but the way the array is declared gives us a clue as to how we could look at it. By having i go from 0-23, we're thinking of each increment of i as representing 6 bits of the array.

    int binary_array[144] = // array to convert to 24 dec
    {//0 1 2 3 4 5 = j
       0,0,0,0,0,0,   //i = 0
       0,0,0,0,0,1,   //i = 1 
       0,0,0,0,1,0,   //i = 2
       0,0,0,0,1,1,   //i = 3
       0,0,0,1,0,0,   //i = 4
       0,0,0,1,0,1,   //i = 5
       0,0,0,1,1,0,   //etc...
       0,0,0,1,1,1,
       0,0,1,0,0,0,
       0,0,1,0,0,1,
       0,0,1,0,1,0,
       0,0,1,0,1,1,
       0,0,1,1,0,0,
       0,0,1,1,0,1,
       0,0,1,1,1,0,
       0,0,1,1,1,1,
       0,1,0,0,0,0,
       0,1,0,0,0,1,
       0,1,0,0,1,0,
       0,1,0,0,1,1,
       0,1,0,1,0,0,
       0,1,0,1,0,1,
       0,1,0,1,1,0,
       0,1,0,1,1,1,
    };

The part where we add j comes after we do i*6, i.e. we've selected an offset that puts us at the beginning of a row. j becomes an offset into that particular row! Hence, the loop for j goes from 0 to 5.

Whew, ok, so we now know that binary_array[i*6 + j] refers to the jth element in the ith row. Once you can convince yourself of how binary_array[i*6 + j] translates to a single element in binary_array, you can examine all the elements around it.

Let's say i = 2, and j = 4. This corresponds to a '1' in the array. Now that we know this, we can restate the line of code like so: temp |= (1) << (5 - j);

Are you familiar with bitwise-or and the bitshifting operators?

[Garion]

I didn't see bitwise or bitshifting on the tutorial from this website. It's all I've looked at so far.

I understand a little of the basics like shifting 0010 left would be 0100.

I'm just not sure how that lines code actually gets processed.

the |= means right to left so I think it means the (5 - j) gets processed first. then it skips the operator << and does the binary_array[i*6 +j] part and shifts it from there?

That didn't sound correct in my head though.

[booradley60]

Let's say i=2 and j=4.
temp |= binary_array[i*6 + j] << (5 - j); becomes
temp |= (1) << (5 - j); as described in my earlier post. This becomes
temp |= (1) << (1); since 5-4=1.
Well, (1) << (1) means take the value on the left side of << (1 in this case) and shift it left. How many times? Well, whatever number is on the right of the << is how many times (also 1 in this case).
1 in binary looks like this:

0000 0001

(likely more zero bits on your platform, but not imporant for demonstration.) Shifting this once to the left yields

0000 0010

Now we have
temp |= 0000 0010; If temp were

0000 1000

(in decimal: 8) then the bitwise-or operator would be applied like this
0000 1000 |= 0000 0010;which produces

0000 1010

The end goal of all this shifting and bitwise-or'ing is that the row in

binary_array

will end up completely stored in

temp

So if we're on i=2, we're looking at a row containing

0,0,0,0,1,0

in

bitwise_array

What will end up in temp is

0000 0010

Great. Now that the value is in temp, we can save temp inside the decimal_array and move on to the next row where we do it all over again.

[Garion]

Thanks for the detailed explanation. I'll refer back to this and read about the bitwise operators.

[Chervil]

I think this is the context:

    // Binary to decimal
    for (int i=0; i<24; i++)
    {
        int temp = 0;

        for (int j = 0; j<6; j++)
            temp |= binary_array[i*6 + j] << (5 - j);

        decimal_array[i] = temp;
    }

There are two different arrays, one has 144 elements, the other has 24. Whichever way you go about things, there has to be a bit of manipulation to synchronise the use of the correct element from each array.

As you see in the outer loop, i goes from 0 to 23, that's pretty ordinary. The inner loop has j going from 0 to 5.

If you work it out, the expression i*6 + j will simply give each value from 0 to 143.

Looking a bit more closely, we then have binary_array[i*6 + j] which will be either a 0 or 1. In order to interpret this as part of a 6-bit binary number, it is shifted left by (5 - j) positions. That is, when j is 0, the bit is shifted left by 5 places (equivalent to multiplication by 32). When j is 5, the bit is not shifted at all (equivalent to multiplication by unity).

Next, this value is combined with the current value of temp using the binary or operator | and last of all, this result is stored in temp, replacing its previous value.

When first learning to code, I found (and still do, many times), that the code is easier to understand if it is spread over many lines, with lots of temporary variables to store intermediate values. That helps with debugging too. The code as it stands does a lot on a single line which I'll admit can make it harder to read and understand - though you'll find with practice it gets easier to mentally juggle such things.

Bitwise Tutorial;
http://www.cprogramming.com/tutorial/bitwise_operators.html