Bootcamp
Search…
A.12: Bit Manipulation

Introduction

Bit manipulation is commonly taught in core computer science courses to help students understand how numbers are represented and manipulated by computers. Some companies use bit manipulation in their interview processes.
Please read about the 6 main bitwise operators &, |, ~, ^, <<, and >> here. These operators can be used in Python to perform bitwise operations.

Use Case: Hamming Codes

A Hamming Code is an error-correction algorithm that uses bit manipulation to check if a set of data has errors (specifically binary data) in O(logn) space and time. These videos give a good intuition of the usefulness of bit manipulation as it relates to binary data.
Hamming codes have a Hamming distance of 3: The algorithm can detect up to three errors per block.

Exercises

Pre-Class

  1. 1.
    1. 1.
      Hint: If A XOR B == C, then C XOR A == B and C XOR B == A.
    2. 2.
      Rocket Academy solution code: https://pastebin.com/BVmPd2kE​
    3. 3.
      Rocket Academy solution video: https://youtu.be/88-cUrvsZ5Q?t=3202​

Part 1

More Comfortable

  1. 1.
    1. 1.
      Requires trick to understand what happens when we XOR a number with 0, and when we XOR a number with itself

Further Reading

Two's complement
Copy link
On this page
Introduction
Use Case: Hamming Codes
Exercises
Pre-Class
Part 1
More Comfortable
Further Reading