User:Fabien Labeyrie/Bit Shifting

Bit Shifting : how i learned to stop worrying and love binary numbers

Here is how to deal with binary numbers when you are programming on an old computer (Basic V 2.0 on Commodore 64) or when you are configuring internal parameters on your arduino board. Thanks to Mr. Stock who made this nightmare looking almost simple.

What is a bit ?

In the binary numeral system, everything looks like 0110010100010100111...
The bit "is the basic unit of information in computing (Wikipedia)". It can be a 1 or a 0.

Bit weight

In a series of bit, each digit has got a particular weight. Let's take a series of 8 bits :

Series = 01010110

         0   1   0   1   0   1   1   0
Weight : 128 64  32  16  8   4   2   1  

Definitions

A series of 4 bits is called a nibble.

A series of 8 bits is called a byte or octet (2 nibbles).

The first digit -128 in the previous example- is called MSB (Most Significant Bit).

The last digit -1 in the previous example- is called LSB (Less Significant Bit).

You can also talk about MSN (Most Significant Nibble) and LSN (Less Significant Nibble).

Big Endian Vs Little Endian

There are two ways to order the bits. Usually for binary numbers we read from right to left. It is called Little Endian because we read the lower bit first. If we read the higher bit first, it is called Big Endian ordering.

<-- Little Endian
Big Endian --> 

What is << (bit shifting) ?

A bit shift consists in moving one or several digits in a line of 0110010100010100111...

Examples

1 << 3

1 = 0001 in the binary numeral system
1 << 3 means we are gonna move the value 1, to the left <<, 3 times.
1 << 3 : 0001  ->  0010  ->  0100  ->  1000   
               1st move  2nd move  3rd move

1 << 3 = 1000 and 1000 in the binary numeral system = 8

7 << 5

7 = 00000111
7 << 5 : 0000 0111  ->  0000 1110  ->  0001 1100  ->  0011 1000  ->  0111 0000  ->  1110 0000 

7 << 5 = 1110000 in the binary numeral system = 224

Logical operations

Logical operations can be used to set or to clear a bit. For more information about logic gates.

Examples

Using the logical operator & (AND)

RegX = 01110011

RegX & (1 << 3)
0111 0011 AND 0000 1000 = 0000 0000 

Setting a bit with | (OR)

RegX = 01110011

RegX | (1 << 3)
0111 0011 OR 0000 1000 = 0111 1011 

Clearing a bit with & (AND) and NOT

RegY = 01011011
NOT(1 << 3) = 11110111

RegY & NOT(1 << 3)
0101 1011 AND 1111 0111 = 0101 0011  

Operators, Hexadecimal and Decimal

AND, NOT, OR and XOR

Operator  Binary       Hexadecimal  Decimal


          0011 0010 =  0x32      =  50
NOT   ->  1100 1101 =  0xCD      =  205 

          0110 1101 =  0x6D      =  104
          0001 1010 =  0x1A      =  26
AND   ->  0000 1000 =  0x08      =  8
   
          0111 1100 =  0x7C      =  124
          0000 0101 =  0x05      =  5
OR    ->  0111 1101 =  0x7D      =  125

          1111 1111 =  0xFF      =  255
          1000 1000 =  0x88      =  136
XOR   ->  0111 0111 =  0x77      =  119

A "Word" ?

In modern computing, a word refers to a group of bits usually 16, 32 or 64.

Examples

16 bit word

Series = 0110101001101100

                                       High byte | Low byte
                                                 |
         0     1     1    0    1    0    1   0   | 0   1  1  0  1 1 0 0
Weight : 32768 16384 8192 4096 2048 1024 512 256 | 128 64 32 16 8 4 2 1 
                                                 |
                                        

The High byte weights 256 times the Low byte.

From a 16 bit word to 2 bytes

When the computer's memory is too small to generate real 16 bit words, they virtually agglomerate 2 bytes together. We can access to those bytes independently:

Hbyte = Word / 256 Lbyte = Word % 256 (% is the modulo)

Examples

257

257 = 00000001 00000001                                       
      Hbyte   Lbyte

Hbyte = 257 / 256 = 1
Lbyte = 257 % 256 = 1                             

260

260 = 00000001 00000100                                       
      Hbyte   Lbyte

Hbyte = 260 / 256 = 1
Lbyte = 260 % 256 = 4                             

From 2 bytes to a 16 bit word

The reverse operation is done by the following formula:

Word = (256 x Hbyte) + Lbyte