loading...

Binary & Bit Manipulation

jjb profile image JB Updated on ・4 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources:

  1. Some plain English fundamentals about bits/bytes/words
  2. Fundamentals of data representation (multi page resource, so make sure to click through each topic)
  3. Binary numbers + bit shifting overview (see links at bottom of the article)
  4. Two's Complement
  5. Sign & Magnitude
  6. Why two's complement is preferred
  7. Video on bitwise operators
  8. Another video on bitwise
  9. 1st bitmasks video
  10. 2nd bitmasks video

Other resources used: Geeksforgeeks, backtobackswe

(Also worth mentioning is this article about a creative use of bitwise operators)

Takeaways:

  • Binary numbers are base-two. The number system most of us are familiar with is base-ten or decimal. Binary numbers are composed of only 1s and 0s.
  • The first bit in a binary number is known as the most-significant-bit, the last bit in a binary number is known as the least-significant-bit (MSB & LSB).
  • 1010 in decimal is one thousand and ten. 1010 in binary is ten. That is because each bit in binary is a sequential power of two, instead of a power of ten. To understand this better, see this article
  • Negative numbers in binary can be represented in a few ways. The most common way is called two's complement.
  • In two's complement we use the first bit of a number to tell us what the sign is (- or +). If the first bit is a 1 then the number is negative. If it's 0 then the number is positive. So 11010, using two's complement, is -6 in decimal (-16 + 8 + 2). Written as 01010, it is ten (8 + 2).
  • Another way to represent negative numbers in binary is called Sign & Magnitude
  • Sign & magnitude is similar to two's complement, where the first bit indicates if the number is positive or negative. However, we never count the first bit towards the number's value.
  • Using sign & magnitude: 1010 is -2 in decimal. 0010 is 2 in decimal
  • Fractions in binary are represented in one of two ways: fixed point & floating point.
  • For fixed point fractions, take an 8-bit number: 10101000. The first 4 bits represent the number left of the decimal point, the trailing 4 bits represent the fractions after the decimal point. So 10101000 can be visualized as 1010.1000 or 10.5. Why .5? well, the four bits after the decimal point represent (in order): 0.5, 0.25, 0.125, 0.0625. So .1000 = 0.5. See here for a more thorough explanation
  • For a floating point number there are 3 components: a sign, exponent, and mantissa. The sign (most-significant-bit) denotes the sign of the number. The exponent portion is after the sign and is the number we should multiply the mantissa by. And the mantissa is the remaining bits. For a more thorough understanding of floating point binary I have found this to be the best explanation
  • We can manipulate bits in a binary number using bitwise operations
  • The bitwise operators are: AND (&), OR (|), Exclusive OR (^) (also referred to as XOR), Left Shift (<<), Right Shift (>>), and NOT (~) (also referred to as one's complement).
  • & takes two bits and returns 1 if both are 1.
  • | takes two bits and returns 1 if either or both are set.
  • ^ takes two bits and returns 1 only if either is set - not both.
  • ~ inverts bits. Example: ~1010 = 0101.
  • << moves bits to the left by a specified amount and appends 0 at the right side. A single << is the same as multiplying by two. Example: 8 << 1 = 10000 (16).
  • >> does the opposite to <<, it shifts bits to the right, and a single right shift is the equivalent to dividing by two. Example: 8 >> 1 = 0100 (4).
  • One important thing about right shifts (>>) is that there are two types: Logical right shift & Arithmetic right shift.
  • Arithmetic right shifts preserve the most-significant-bit (it is copied and the copy is retained at the original position). This is important for two's complement (also for sign & magnitude), as it preserves the number's sign.
  • Logical right shifts do not retain the most-significant-bit, and instead just pad/insert 0s.
  • Arithmetic right shift example: 11000 >> 1 = 11100
  • Logical right shift example: 11000 >> 1 = 01100
  • In C# right shifts (>>) are arithmetic, unless the integer is unsigned - then they are logical. In Java there are two right shift operators: >> is arithmetic, and >>> is logical.
  • An unsigned integer is always positive and we calculate it's value based on all of its bits. Meaning we always include the most-significant-bit when summing the set bits (1s). Unsigned integers, therefore, have a greater possible positive value than a signed integer.
  • A signed integer uses the first bit (most-significant-bit) to identify the integer as positive or negative (usually using two's complement). This means signed integers can be negative or positive, but their maximum positive value is less than that of an unsigned integer.
  • This is a helpful SO post on signed vs unsigned integers
  • A common tool used when manipulating bits is something called a bitmask
  • A bitmask is just another binary number that is used to help retain/toggle/clear/set bits in another number. Please see the related resources, or the below code sample for some examples that show the use of bitmasks.

Below you will find some common bit manipulations. I have included comments to explain the operations + provide context:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Dec 23 '19 by:

Discussion

markdown guide
 

Suggest more info on MSB and LSB, image pointing to bits, also there are different memory formats that can cause the bit order to be inverted depending on the perspective. E.g. binary files and communications.

 

@andrewharpin thanks for the suggestions and you are absolutely right - there is much more to cover/explain.

For this post (and my week learning the material) I only covered the basics and tried to focus on things that might come up in a FAANG style SWE interview.

 

Only ensuring those learning understand that there is still more to learn. :-)