Rocket Academy Bootcamp
  • 🚀Welcome to Bootcamp!
  • 🛠️Logistics
    • Course Schedules
    • Course Methodology
    • Required Software
    • LinkedIn Education Badge
  • 📚General Reference
    • Naming, Casing, and Commenting Conventions
    • VS Code Tips
    • Recommended Resources
  • 🪨0: Foundations
    • 0.1: Command Line
    • 0.2: Git
      • 0.2.1: Branches
    • 0.3: GitHub
      • 0.3.1: Pull Requests
    • 0.4: JavaScript
      • 0.4.1: ES6
      • 0.4.2: Common Syntax
      • 0.4.3: Reference vs Value
      • 0.4.4: Classes
      • 0.4.5: Destructuring and Spread Operator
      • 0.4.6: Promises
        • 0.4.6.1: Async Await
    • 0.5: Node.js
      • 0.5.1: Node Modules
      • 0.5.2: NPM
      • 0.5.3: Nodemon
  • 🖼️1: Frontend
    • 1.1: HTML
    • 1.2: CSS
      • 1.2.1: Layout
    • 1.3: React
      • Styling in ReactJs
      • Using Styling Libraries with React
      • React Deployment
    • 1.E: Exercises
      • 1.E.1: Recipe Site
      • 1.E.2: Portfolio Page
      • 1.E.3: World Clock
      • 1.E.4: High Card
      • 1.E.5: Guess The Word
    • 1.P: Frontend App
  • 🏭2: Full Stack
    • 2.1: Internet 101
      • 2.1.1: Chrome DevTools Network Panel
      • 2.1.2: HTTP Requests and Responses
    • 2.2: Advanced React
      • 2.2.1: AJAX
      • 2.2.2: React Router
      • 2.2.3: useContext
      • 2.2.4: useReducer
      • 2.2.5: Environmental Variables
      • 2.2.6: React useMemo - useCallback
    • 2.3: Firebase
      • 2.3.1: Firebase Realtime Database
      • 2.3.2: Firebase Storage
      • 2.3.3: Firebase Authentication
      • 2.3.4: Firebase Hosting
      • 2.3.5: Firebase Techniques
    • 2.E: Exercises
      • 2.E.1: Weather App
      • 2.E.2: Instagram Chat
      • 2.E.3: Instagram Posts
      • 2.E.4: Instagram Auth
      • 2.E.5: Instagram Routes
    • 2.P: Full-Stack App (Firebase)
  • 🤖3: Backend
    • 3.1: Express.js
      • 3.1.1 : MVC
    • 3.2: SQL
      • 3.2.1: SQL 1-M Relationships
      • 3.2.2: SQL M-M Relationships
      • 3.2.3: SQL Schema Design
      • 3.2.4: Advanced SQL Concepts
      • 3.2.5: SQL - Express
      • 3.2.6: DBeaver
    • 3.3: Sequelize
      • 3.3.1: Sequelize One-To-Many (1-M) Relationships
      • 3.3.2: Sequelize Many-To-Many (M-M) Relationships
      • 3.3.3: Advanced Sequelize Concepts
      • 3.3.4 Database Design
    • 3.4: Authentication
      • 3.4.1: JWT App
    • 3.5: Application Deployment
    • 3.E: Exercises
      • 3.E.1: Bigfoot JSON
      • 3.E.2: Bigfoot SQL
      • 3.E.3: Bigfoot SQL 1-M
      • 3.E.4: Bigfoot SQL M-M
      • 3.E.5: Carousell Schema Design
      • 3.E.6: Carousell Auth
    • 3.P: Full-Stack App (Express)
  • 🏞️4: Capstone
    • 4.1: Testing
      • 4.1.1: Frontend React Testing
      • 4.1.2: Backend Expressjs Testing
    • 4.2: Continuous Integration
      • 4.2.1 Continuous Deployment (Fly.io)
      • 4.2.2: Circle Ci
    • 4.3: TypeScript
    • 4.4: Security
    • 4.5: ChatGPT for SWE
    • 4.6: Soft Skills for SWE
    • 4.P: Capstone
  • 🧮Algorithms
    • A.1: Data Structures
      • A.1.1: Arrays
        • A.1.1.1: Binary Search
        • A.1.1.2: Sliding Windows
      • A.1.2: Hash Tables
      • A.1.3: Stacks
      • A.1.4: Queues
      • A.1.5: Linked Lists
      • A.1.6: Trees
      • A.1.7: Graphs
      • A.1.8: Heaps
    • A.2: Complexity Analysis
    • A.3: Object-Oriented Programming
    • A.4: Recursion
    • A.5: Dynamic Programming
    • A.6: Bit Manipulation
    • A.7: Python
  • 💼Interview Prep
    • IP.1: Job Application Strategy
    • IP.2: Resume
    • IP.3: Portfolio
Powered by GitBook
On this page
  • Learning Objectives
  • Introduction
  • Exercises
  • Pre-Class
  • Part 1
  • Part 2
  • More Comfortable
  1. Algorithms

A.6: Bit Manipulation

PreviousA.5: Dynamic ProgrammingNextA.7: Python

Learning Objectives

  1. Understand that computers store values in code as sequences of bits (data type with value 0 or 1). Computers represent numbers with bits in .

  2. Bit manipulation refers to manipulation of the bits that form a value using bitwise operators

  3. Know the 6 most common bitwise operators (&, |, ~, ^, <<, and >>) and what they do

Introduction

Computers store all data as sequences of 0s and 1s in a data type called a "bit". Programming languages like JavaScript automatically translate JavaScript to bits for us, thus we rarely need to think of bits while building apps. However, there are occasionally tested in interviews that can be solved more efficiently by manipulating bits with bitwise operators instead of usual JavaScript commands, thus we learn bit manipulation.

Bit manipulation refers to changing bits in a value using bitwise operators. In the algorithm interview context, this typically involves manipulating bits that represent numbers.

There are 6 most common bitwise operators: &, |, ~, ^, <<, and >>. Let us examine them in a table.

Operator
Name
Example
Description

&

Bitwise And

a & b

Compare bits of values a and b and produce a result based on the comparison. In the result, bits in each position that were both 1 in a and b stay 1, otherwise become 0.

|

Bitwise Or

a | b

Compare bits of values a and b and produce a result based on the comparison. In each bit of the result, if either a or b had a 1 bit in that position, that bit is now 1.

~

Bitwise Not

~a

Produce a result where all bits in a are reversed. If any bit in a was 0, the same bit in the result is 1 and vice versa.

^

Bitwise Xor (pronounced "x-or" or "exclusive or")

a ^ b

Same as Bitwise Or, except if the same bit in both values is 1, that bit is 0 in the result.

<<

Bitwise Left Shift

a << 1

Shift all bits in a to the left by the number to the right of the operator, inserting a 0 bit to the right of the original number for every shift.

>>

Bitwise Right Shift

a >> 1

Shift all bits in a to the right by the number to the right of the operator, deleting the right-most bit of the original number with every shift.

Before trying bitwise operators on your own in a Node console, read the following article with diagrams on how each operator works, and watch the following illustrative videos.

Exercises

Pre-Class

    1. Hint: If A XOR B == C, then C XOR A == B and C XOR B == A.

Part 1

Part 2

More Comfortable

    1. Hint: Unsigned integer means the number is always positive and has no signed bit

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

Decode XORed Array ()

(Python)

(Python)

Hint: For JavaScript, consider using the built-in method on numbers to convert integers (aka decimal numbers) to binary numbers, and toString(10) to convert binary numbers to integers. For Python, consider using the equivalent built-in functions bin and int.

XOR Operation in an Array ()

Hamming Distance ()

Sort Integers by the Number of 1 Bits ()

Binary Number with Alternating Bits ()

Power of Two ()

Power of Four ()

Number Complement ()

Hint: We cannot just use the ~ operator because JavaScript and Python integers are signed by default, and the problem assumes unsigned integers. .

Convert Binary Number in a Linked List to Integer ()

Maximizing Xor ()

Sum vs Xor ()

Reverse Bits (, )

Single Number (, )

🧮
LeetCode
Rocket Academy solution code
Rocket Academy solution video
toString(2)
LeetCode
LeetCode
LeetCode
LeetCode
LeetCode
LeetCode
LeetCode
Solution here
LeetCode
HackerRank
HackerRank
HackerRank
LeetCode
HackerRank
LeetCode
binary format
several algorithm problems
Understanding Bitwise OperatorsCode Envato Tuts+
Understanding Bitwise Operators
Introduction to basic bitwise operators and how they can be used in practice
Deeper introduction to binary numbers and how to manipulate those numbers using bitwise operators
Example of how to add 2 numbers using only bitwise operators
Logo