C Bitwise operations left shift and bitwise OR

Question

Very short, I am having issues understanding the workings of this code, it is much more efficient then my 20 or so lines to get the same outcome. I understand how left shift is supposed to work and the bitwise Or but would appreciate a little guidance to understand how the two come together to make the line in the for loop work. Code is meant to take in an array of bits(bits) of a given size(count) and return the integer value of the bits.

unsigned binary_array_to_numbers(const unsigned *bits, size_t count) {
    unsigned res = 0;
    for (size_t i = 0; i < count; i++)
        res = res << 1 | bits[i]; 
    return res;
}

EDIT: As requested, My newbie solution that still passed all tests: Added is a sample of possible assignment to bits[]

unsigned binary_array_to_numbers(const unsigned *bits, size_t count)
{
        int i, j = 0;
        unsigned add = 0;
        for (i = count - 1; i >= 0; i--){
                if(bits[i] == 1){
                        if(j >= 1){
                                j = j * 2;
                                add = add + j;
                        }
                        else{
                                j++;
                                add = add + j;

                        }
                }
                else {
                        if( j>= 1){
                                j = j * 2;
                        }
                        else{
                                j++;
                        }
                }
        }

        return add;
}

void main(){
        const unsigned bits[] = {0,1,1,0};
        size_t count = sizeof(bits)/sizeof(bits[0]);
        binary_array_to_numbers(bits, count);
}

Two Down Votes? Maybe I don't understand how this site is supposed to work? I thought stack overflow was meant to be for **specific** code related questions. This post here https://stackoverflow.com/questions/141525/what-are-bitwise-shift-bit-shift-operators-and-how-do-they-work?rq=1 is an all time classic with 1230 upvotes and it is essentially "How does bit-shifting work?" A general question with answers that could be found many other places. I am posting about a specific use case, why the downvotes? — DocSpiegel, Dec 03 '18 at 04:12
Yes, it was the number one ranked answer for one of the C katas on CodeWars. When you submit an answer there it is tested very thoroughly to pass all edge cases. Just realized I changed the return type during testing to int, just changed it back, I have double checked the code is identical to the original answer now. — DocSpiegel, Dec 03 '18 at 04:48
Could you explain conceptually what you expect the code to do by working through a concrete example? — Mad Physicist, Dec 03 '18 at 06:19
I marked answer of Dagan as accepted, he stepped through the loop iterations explaining the operations and changes. This is expected functioning of code, I just needed help getting over the mental block. — DocSpiegel, Dec 03 '18 at 14:50

score 1 · Accepted Answer · answered Dec 03 '18 at 10:34

a breakdown:

every left shift operation on a binary number effectively multiplies it by 2 0111(7) << 1 = 1110(14)
consider rhubarbdog answer - the operation can be seen as two separate actions. first left-shift (multiply by two) and then OR with the current bit being reviewed
the PC does not distinguish between the value displayed and the binary representation of the number

lets try and review a case in-which your input is:

bits = {0, 1, 0, 1};
count = 4;
unsigned binary_array_to_numbers(const unsigned *bits, size_t count) {
    unsigned res = 0;
    for (size_t i = 0; i < count; i++)
        res = res << 1 // (a)
        res = res | bits[i]; /* (b) according to rhubarbdog answer */
    return res;
}

iteration 0:
- bits[i] = 0;
- (a) res = b0; (left shift of 0)
- (b) res = b0; (bitwise OR with 0)

iteration 1:
- bits[i] = 1;
- (a) res = b0; (left shift of 0)
- (b) res = b1; (bitwise OR with 1)

iteration 2:
- bits[i] = 0;
- (a) res = b10; (left shift of 1 - decimal value is 2)
- (b) res = b10; (bitwise OR with 0)

iteration 3:
- bits[i] = 1;
- (a) res = b100; (left shift of 1 - decimal value is 4)
- (b) res = b101; (bitwise OR with 1)

the final result for res is binary(101) and decimal(5) as one would expect NOTE: the use of unsigned is a must since a signed value will be interpreted as a negative value if the MSB is 1

hope that helps...

This is what I needed, this makes sense now when explained step by step. Sometimes something seems clear as day to one person who is familiar but to a newcomer it just doesn't click. Appreciate your taking the time to help. — DocSpiegel, Dec 03 '18 at 14:46

phil · Answer 2 · 2018-12-03T04:57:02.887

0

consider them as 2 operations i'll re-write res= ... as 2 lines

res = res << 1
res = res | 1

The firs pass res gets set to 1, next time it's shifted *2 then because it's now even +1

edited Dec 03 '18 at 04:57

answered Dec 03 '18 at 03:11

phil

561
3
10

So if `bits[i]` is 1 then it is OR'd by 1 so it remains 1 and `shift` is 1 then if `res` is 0 then how does res get a value? My confusion is with this, so you shift res(0) by shift(1). Is 0 shifted left by one not still 0? I am sorry I have a logic gap here, could you fill it in for me? – DocSpiegel Dec 03 '18 at 04:31
I know that leftshift is equivalent to left operand * 2^right operand. But 0 * 2^1 is 0. I am missing something. – DocSpiegel Dec 03 '18 at 04:43
@DocSpiegel i've edited my answer, you may want to look again – phil Dec 03 '18 at 05:13
I will accept answer if you can quickly explain how, if res = 0 so 0000 0000 how does leftshifting it make it 1? Wouldn't that just cause one 0 to fall off and be replaced by another on the other end? – DocSpiegel Dec 03 '18 at 05:49
the left shift doesn't make it 1 it's the bitwise or of 1 `res = res | 1` – phil Dec 03 '18 at 09:45

C Bitwise operations left shift and bitwise OR

2 Answers2