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