Bit array in c doubt

Question

People were looking at some examples of bit array and saw the following function:

char get_bit(char *array, int index)
{

    return 1 & (array[index / 8] >> (index % 8));
}

I couldn’t understand why the author used >> instead of << to return a bit.

Answer 1

In an Array of bytes, each of them occupies a memory position.

Each byte has 8 bits. That is, in each position of the array we have eight bits, so we have to have a way to get each one individually.

To make it easier, let’s view each bit at your address:

byte                  10100111 10010001 01101111 01111111 ....
                                            ^- usaremos o bit 19 como exemplo

endereço de memória   n        n+1      n+2      n+3      ...

posição do bit:       7......0 15.....8 23....16 31....24 ...
(bit menos significante para a direita)

Note that at every 8 bit positions, we advance 1 memory position. Therefore, to know the position of the bit in memory, we need to divide the position of the bit by 8. Here comes this part of the code:

return 1 & (array[index / 8] >> (index % 8));
                  ^^^^^^^^^

Ok, in our example, bit 19 is at 19 / 8, which gives 2 (in integers). We already know then that we have to read the address n+2, that has this value:

0b01101111

Good, our index is 19. We’ve already used 19 to get the n+2, dividing by 8, but we have to know where the right bit is. For this we take 19 % 8, which is this part of the code:

return 1 & (array[index / 8] >> (index % 8));
                                 ^^^^^^^^^

If it was my code, I’d probably use it index & 7, for the sake of taste, but in the end it is the same. In this case, the value returned is 3

Therefore, our "calculation" was like this:

return 1 & ( 0b01101111 >> 3 )
                   ^

The operator >> displaces the 3x byte to the right, after all, who implemented the function opted by counting from right to left:

return 1 & ( 0b00001101 )
                      ^

Finally the 1 & will discard the rest of the byte and return only our bit 19, which in case is 1.

When you do the reverse, it is set or reset the bit, will just use the opposite operator, the <<, to set the bit in its right position, something more or less like this (can be optimized, and may have some silly mistake, was just example):

array[index / 8] = array[index / 8] & ~(1 << (index % 8)) | (bit & 1) << (index % 8);

And if the person had chosen the most significant on the right?

11100101 10001001 11110110 11111110 ...
0......7 8.....15 16....31
                     ^

Simple, the formula would be something like this:

return 127 & ( array[index / 8] << (index % 8) ) / 127;

And this would happen:

return 127 & ( 0b11110110 << 3 ) / 127;
                    ^

Reducing to this:

return 127 & ( 0b10110000 ) / 127
                 ^

What would give 1 likewise.

If you want more details from the operator >>, here is a brief explanation:

What are the operators for | & << >>?

_{^{(It’s not the same language, but it’s the same working.)}}

Answer 2

<< is used to define a value, and >> to get the value.