# A.6: Bit Manipulation

## Learning Objectives

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

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

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 several algorithm problems 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 |
| Compare bits of values |

| Bitwise Or |
| Compare bits of values |

| Bitwise Not |
| Produce a result where all bits in |

| Bitwise Xor (pronounced "x-or" or "exclusive or") |
| Same as Bitwise Or, except if the same bit in both values is 1, that bit is 0 in the result. |

| Bitwise Left Shift |
| Shift all bits in |

| Bitwise Right Shift |
| Shift all bits in |

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

Decode XORed Array (LeetCode)

Hint: If

`A XOR B == C`

, then`C XOR A == B`

and`C XOR B == A`

.Rocket Academy solution code (Python)

Rocket Academy solution video (Python)

### Part 1

Hint: For JavaScript, consider using the built-in `toString(2)`

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 (LeetCode)

Hamming Distance (LeetCode)

Sort Integers by the Number of 1 Bits (LeetCode)

Binary Number with Alternating Bits (LeetCode)

### Part 2

Power of Two (LeetCode)

Power of Four (LeetCode)

Number Complement (LeetCode)

Hint: We cannot just use the

`~`

operator because JavaScript and Python integers are signed by default, and the problem assumes unsigned integers. Solution here.

Convert Binary Number in a Linked List to Integer (LeetCode)

### More Comfortable

Maximizing Xor (HackerRank)

Sum vs Xor (HackerRank)

Reverse Bits (HackerRank, LeetCode)

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

Single Number (HackerRank, LeetCode)

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

Last updated