A.6: Bit Manipulation

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 binary format.

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 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	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.

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

Exercises

Pre-Class

1. Decode XORed Array (LeetCode)

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

   2. Rocket Academy solution code (Python)
   3. 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.

1. XOR Operation in an Array (LeetCode)
2. Hamming Distance (LeetCode)
3. Sort Integers by the Number of 1 Bits (LeetCode)
4. Binary Number with Alternating Bits (LeetCode)

Part 2

1. Power of Two (LeetCode)
2. Power of Four (LeetCode)
3. Number Complement (LeetCode)

   1. Hint: We cannot just use the ~ operator because JavaScript and Python integers are signed by default, and the problem assumes unsigned integers. Solution here.
4. Convert Binary Number in a Linked List to Integer (LeetCode)

More Comfortable

1. Maximizing Xor (HackerRank)
2. Sum vs Xor (HackerRank)
3. Reverse Bits (HackerRank, LeetCode)

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

4. Single Number (HackerRank, LeetCode)

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