Lab 03 Examples¶

Click <shift> <enter> in each code cell to run the code. Be sure to start with the #include directives to load the required libraries.

In [1]:
// For Lab 03, we are limited to these includes.
// Other libraries that can do the set or binary operations for us are not allowed.
// For example, DO NOT include <bitset> or <set>.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

The Left Shift and Right Shift Bitwise Operators¶

In previous weeks, we have looked at AND &, OR |, XOR ^, and NOT ! operators.

We have also looked at the distinction between the logical operators && and || versus the bitwise operators & and |.

Today we will look at the left shift << and right shift >> bitwise operators.

  • The left shift operator << shifts all bits to the left by a specified number of positions.
  • Each left shift effectively multiplies the number by 2.
  • The right shift operator >> shifts all bits to the right by a specified number of positions.
  • Each right shift effectively divides the number by 2, truncating any remainder. This means that the least significant bit (rightmost bits) is discarded.
Original Operation Result Decimal
00001 1 << 1 00010 1 << 1 = 2
00001 1 << 2 00100 1 << 2 = 4
00001 1 << 3 01000 1 << 3 = 8
01000 8 >> 1 00100 8 >> 1 = 4
01000 8 >> 2 00010 8 >> 2 = 2
01000 8 >> 3 00001 8 >> 3 = 1
In [2]:
std::cout << "1 << 1 = " << (1 << 1) << std::endl;
std::cout << "1 << 2 = " << (1 << 2) << std::endl;
std::cout << "1 << 3 = " << (1 << 3) << std::endl;
std::cout << "8 >> 1 = " << (8 >> 1) << std::endl;
std::cout << "8 >> 2 = " << (8 >> 2) << std::endl;
std::cout << "8 >> 3 = " << (8 >> 3) << std::endl;

1 << 1 = 2
1 << 2 = 4
1 << 3 = 8
8 >> 1 = 4
8 >> 2 = 2
8 >> 3 = 1
Original Operation Result Decimal
00011 3 << 1 00110 3 << 1 = 6
00101 5 << 2 10100 5 << 2 = 20
01100 12 >> 1 00110 12 >> 1 = 6
01101 13 >> 2 00011 13 >> 2 = 3
10110 22 >> 3 00010 22 >> 3 = 2
11111 31 >> 4 00001 31 >> 4 = 1
10000 16 >> 2 00100 16 >> 2 = 4
In [3]:
std::cout << "3 << 1 = " << (3 << 1) << std::endl;
std::cout << "5 << 2 = " << (5 << 2) << std::endl;
std::cout << "12 >> 1 = " << (12 >> 1) << std::endl;
std::cout << "13 >> 2 = " << (13 >> 2) << std::endl;
std::cout << "22 >> 3 = " << (22 >> 3) << std::endl;
std::cout << "31 >> 4 = " << (31 >> 4) << std::endl;
std::cout << "16 >> 2 = " << (16 >> 2) << std::endl;

3 << 1 = 6
5 << 2 = 20
12 >> 1 = 6
13 >> 2 = 3
22 >> 3 = 2
31 >> 4 = 1
16 >> 2 = 4

Programmatically Converting a Bit String to a Base10 Number¶

This first example uses powers and addition.¶

Convert the binary array {1, 1, 1, 0, 0, 1} to decimal.

Binary Digits and Their Corresponding Powers of 2:¶

Index Binary Digit Power of 2 Value
0 1 2⁵ = 32 1 × 32 = 32
1 1 2⁴ = 16 1 × 16 = 16
2 1 2³ = 8 1 × 8 = 8
3 0 2² = 4 0 × 4 = 0
4 0 2¹ = 2 0 × 2 = 0
5 1 2⁰ = 1 1 × 1 = 1

Now, add the values:¶

32 + 16 + 8 + 0 + 0 + 1 = 57

Final Answer:
The binary number 111001 is equal to 57 in decimal.

In [4]:
const int SIZE = 6;
int arr[] = {1, 1, 1, 0, 0, 1};
int decimal = 0;

/*
    1 * 2^(6-1-0) = 32, at i = 0, decimal goes from  0 to 32
    1 * 2^(6-1-1) = 16, at i = 1, decimal goes from 32 to 48
    1 * 2^(6-1-2) =  8, at i = 2, decimal goes from 48 to 56
    0 * 2^(6-1-3) =  0, at i = 3, decimal goes from 56 to 56
    0 * 2^(6-1-4) =  0, at i = 4, decimal goes from 56 to 56
    1 * 2^(6-1-5) =  1, at i = 5, decimal goes from 56 to 57
*/

for (int i = 0; i < SIZE; i++) {
    if (arr[i]) {
        decimal += std::pow(2, SIZE - 1 - i);
    }
}
std::cout << "Decimal value: " << decimal << std::endl;

Decimal value: 57

This second example uses a left shift and the bitwise OR (|).¶

Convert the binary array {1, 1, 1, 0, 0, 1} to decimal using left shift and bitwise OR (|)¶

Step Current Decimal
(Binary)		 Shifted Left
(decimal << 1)
Decimal (Binary)		 Bit to OR OR Operation
(shifted | bit)
Binary		 Result
Decimal (Binary)
i = 0 0
(000000)		 0
(000000)		 1 000000 | 000001 = 000001 1
(000001)
i = 1 1
(000001)		 2
(000010)		 1 000010 | 000001 = 000011 3
(000011)
i = 2 3
(000011)		 6
(000110)		 1 000110 | 000001 = 000111 7
(000111)
i = 3 7
(000111)		 14
(001110)		 0 001110 | 000000 = 001110 14
(001110)
i = 4 14
(001110)		 28
(011100)		 0 011100 | 000000 = 011100 28
(011100)
i = 5 28
(011100)		 56
(111000)		 1 111000 | 000001 = 111001 57
(111001)
  • Start with decimal = 0.
  • For each bit in the array, shift the current decimal value left by 1 (multiply by 2), then use bitwise OR (|) to add the next bit.
  • After processing all bits, the final decimal value is 57.

Final Answer:
The binary number 111001 is equal to 57 in decimal using the left shift and bitwise OR method.

In [5]:
const int SIZE = 6;
int arr[] = {1, 1, 1, 0, 0, 1};
int decimal = 0;

/*
     0 << 1 | 1 =  1, at i = 0      00000 << 1 = 000000, then 000000 | 0000001 =      1, decimal goes from  0 to  1
     1 << 1 | 1 =  3, at i = 1      00001 << 1 = 000010, then 000010 | 0000001 =     11, decimal goes from  1 to  3
     3 << 1 | 1 =  7, at i = 2      00011 << 1 = 000110, then 000110 | 0000001 =    111, decimal goes from  3 to  7
     7 << 1 | 0 = 14, at i = 3      00111 << 1 = 001110, then 001110 | 0000000 =   1110, decimal goes from  7 to 14
    14 << 1 | 0 = 28, at i = 4      01110 << 1 = 011100, then 011100 | 0000000 =  11100, decimal goes from 14 to 28
    28 << 1 | 1 = 57, at i = 5      11100 << 1 = 111000, then 111000 | 0000001 = 111001, decimal goes from 28 to 57
*/

for (int i = 0; i < SIZE; i++) {
    decimal = (decimal << 1) | arr[i];
}
std::cout << "Decimal value: " << decimal << std::endl;

Decimal value: 57

Determining Parity Group Membership using Bitwise AND (&) and Recalculating Parity Bits Using XOR (^)¶

Last week we saw how the bitwise AND (&) operator can be used to determine if a given index is a member of a parity group.

Parity Group 1 Bit Mask Decimal Equivalent Membership
001 & 001 = 0011 & 1 = 1Group 1 Parity Bit
001 & 010 = 0001 & 2 = 0NOT In Group
001 & 011 = 0011 & 3 = 1In Group
001 & 100 = 0001 & 4 = 0NOT In Group
001 & 101 = 0011 & 5 = 1In Group
001 & 110 = 0001 & 6 = 0NOT In Group
001 & 111 = 0011 & 7 = 1In Group
Parity Group 2 Bit Mask Decimal Equivalent Membership
010 & 001 = 002 & 1 = 0NOT In Group
010 & 010 = 102 & 2 = 2Group 2 Parity Bit
010 & 011 = 102 & 3 = 2In Group
010 & 100 = 002 & 4 = 0NOT In Group
010 & 101 = 002 & 5 = 0NOT In Group
010 & 110 = 102 & 6 = 2In Group
010 & 111 = 102 & 7 = 2In Group
Parity Group 4 Bit Mask Decimal Equivalent Membership
100 & 001 = 0004 & 1 = 0NOT In Group
100 & 010 = 0004 & 2 = 0NOT In Group
100 & 011 = 0004 & 3 = 0NOT In Group
100 & 100 = 1004 & 4 = 4Group 4 Parity Bit
100 & 101 = 1004 & 5 = 4In Group
100 & 110 = 1004 & 6 = 4In Group
100 & 111 = 1004 & 7 = 4In Group
In [6]:
const int BLOCK_SIZE = 8;
int codeword_recalculated[] = {0, 1, 0, 1, 0, 1, 1, 1}; // received with error at index 6

for (int i = 1; i < BLOCK_SIZE; i <<= 1) { // loops through the parity bits at each power of 2
    codeword_recalculated[i] = 0;
    for (int j = 1; j < BLOCK_SIZE; j++) { // loops through the entire codeword
        if (j & i) {  // if the jth index is a member of the ith parity group
            codeword_recalculated[i] ^= codeword_recalculated[j]; // recalculate the parity bits
        }
    }
}

std::cout << "Recalculated Parity Bits: ";
for (int i = 1; i < BLOCK_SIZE; i++) {
    std::cout << codeword_recalculated[i] << " ";
}
std::cout << std::endl;

Recalculated Parity Bits: 1 1 1 1 1 1 1

Isolating the Hamming Code Error Index¶

Last week we looked at the following lines of pseudocode.

  x = 0
  x = x | ( (codeword[power(2, i)] ^ codeword_recalculated[power(2, i)]) * power(2, i) )
  • Here we initialize the error index to 0, which assumes there is no error until we find one.
  • We then loop through the parity bits. In Hamming Code (7,4), there are 3 parity bits (at indexes 1, 2, and 4).
    • At each parity bit, we use ^ to compare the parity bits from the received message with the corresponding recalculated parity bit. A true means the group is suspicious.
    • The powers give us the index of the current parity bit.
    • Multiplying (*) the truth value with pow(2, i) effectively shifts the truth value (which is 1 or 0), i positions to the left. If the group is suspicious, the binary index of the error will have a 1 in the i-th bit column. If the group is not suspicious, the binary index of the error (if there is one) will have a 0 in the i-th bit column.
    • The bitwise (|) allows us to build the error index parity bit by parity bit.

This table demonstrates how the bitwise OR (|) and XOR (^) operators work together to isolate the error index.¶

i pow(2, i) codeword[ pow(2, i) ] codeword_recalc[ pow(2, i) ] XOR ( ^ ) * pow(2, i) Err Index ( | )
0 1 1 1 1 ^ 1 = 0 0 * 1 = 0 000 | 000 = 000
1 2 0 1 0 ^ 1 = 1 1 * 2 = 0102 0102 | 000 = 0102
2 4 0 1 0 ^ 1 = 1 1 * 4 = 1002 1002 | 0102 = 1102
In [7]:
int codeword[]              = {0, 1, 0, 1, 0, 1, 1, 1}; // received codeword with error at index 6
int codeword_recalculated[] = {0, 1, 1, 1, 1, 1, 1, 1}; // parity bits recalculated

const int NUM_PARITY_BITS = 3;
int error_index = 0;

// Why is the power function's return value cast to an int?  static_cast<int>(pow(2, i))
for (int i = 0; i < NUM_PARITY_BITS; i++) {
    error_index = error_index | ((codeword[static_cast<int>(pow(2, i))] ^ codeword_recalculated[static_cast<int>(pow(2, i))]) * static_cast<int>(pow(2, i)));
}

std::cout << "Error index: " << error_index << std::endl;

Error index: 6
i 1 << i codeword[ 1 << i ] codeword_recalc[ 1 << i ] XOR ( ^ ) << i Err Index ( | )
0 1 1 1 1 ^ 1 = 0 0 << 0 = 0 000 | 000 = 000
1 2 0 1 0 ^ 1 = 1 1 << 1 = 0102 0102 | 000 = 0102
2 4 0 1 0 ^ 1 = 1 1 << 2 = 1002 1002 | 0102 = 1102
In [8]:
int codeword[]              = {0, 1, 0, 1, 0, 1, 1, 1}; // received codeword with error at index 6
int codeword_recalculated[] = {0, 1, 1, 1, 1, 1, 1, 1}; // parity bits recalculated

const int NUM_PARITY_BITS = 3;
int error_index = 0;

for (int i = 0; i < NUM_PARITY_BITS; i++) {
    error_index = error_index | ((codeword[1 << i] ^ codeword_recalculated[1 << i]) << i);
}

std::cout << "Error index: " << error_index << std::endl;

Error index: 6