Shift operations

Question

I saw the following posted by one of the fellow stackoverflower and it sort of dumbfounds me.

Would someone explain the shifting operations in the following code snippet:

std::vector<bool> a;
a.push_back(true);
a.push_back(false);
//...
for (auto it = a.begin(); it != a.end();) // see 0x for meaning of auto
{
    unsigned b = 0;
    for (int i = 0; i < 8*sizeof(b); ++i)
    {
        b |= (*it & 1) << (8*sizeof(b) - 1 - i);
        ++it;
    }
    // flush 'b'
}

Answer 1

Hi,

8 * sizeof(b) is the number of bits that can be stored in 'b' (which is an unsigned int, i.e. typically 32 or 64 bits).

What the code is doing is that it is packing the boolean values in vector 'a' to become bits in 'b'.

"*it & 1" evalutes to 1 if the boolean value at *it is TRUE, otherwise 0. The bit is then shifted left 32 bits minus 1 minus the index 'i', i.e. shifted left from zero to 31 bits. This means now that the first element of 'a' will control the most significant bit on 'b' (left shift 31), the second element the second most significant bit on 'b' (left shift 30) etc. Note that in C the shifts are arithmetic, i.e. regardless of the byte or bit order, x << 1 is always x * 2.

So for example, if your vector has the first and the 30th element set, 'b' should contain by the end of the day the binary number 10000000 00000000 00000000 00000100.

Answer 2

antti.huima's answer looks right to me.

However there may be a bug in the procedure. The outer loop goes from a.begin to a.end, however the inner loop increments "it" regardless of whether this causes "it" to go past a.end.

if you pass a vector with an "odd" size, say 33 entries, the result could be incorrect.

This may not be a bug if the size of the vector is guarenteed (but maybe there should be test that the length is valid).

Answer 3

What's happening there:

(*it & 1)

this should be 0 or 1 depending on the bool being true or false; note, however, that bools are always 0 or 1 so this could just be (unsigned)*it

<< (8*sizeof(b) - 1 - i)

This is a shift, which moves the bit from thi rightmost position to the i-th from the left. We are shifting a number which has at most one bit set, so this will have the i-th leftmost bit set or not. The rest of the bits are zero.

b |= ...

this sets those bits in b, that are on in the RHS.

i++;

Go to the next input number. Be careful to stay in the input range.

Which means the whole thing will set bits in b, corresponding to the vector elements that are true.