Skip to main content

Bit Manipulation

Bit manipulation represents the elegant and concise facet of algorithms. Apparently, it is based on how the computer stores the information. With such down-to-the-bottom level data structures or operations, the space usage is usually the minimum. The least usage of space makes the speed fast as well.

The unit is bit, which only has two possible values, 0 or 1 (which is exactly the reason that the base is 2, or binary). For the integer data type (int) in most computer system nowadays, there are 32 bits. 

Byte is different from bit. Each byte has 8 bits (so one integer has 4 bytes in size). Thus, the value range of a byte is in [0, 2^8 = 256) (if you know ACII code before, have you ever ask why the range is [0, 256)?). This connects to some very common words used daily,

 1 KB is (2^10 = 1024 ~ 10^3) byte

 1 MB is (2^10 = 1024 ~ 10^3) KB

 1 GB is (2^10 = 1024 ~ 10^3) MB

 1 TB is (2^10 = 1024 ~ 10^3) GB

If we have an integer array with a size of 10^6, the total size is 4*10^6 ~ 4 MB. If you have a movie which is about 100 GB in size, the number of bits in it can also be estimated (homework...).

Now let move on to the negative numbers, which is related to signed numbers. For the signed numbers, the bit on the most left is the flag bit. When it is 0, it is non-negative; when it is 1. it is a negative number. Thus, for the signed integer, the range is [-2^31, 2^31), or

INT_MIN = -2^31

INT_MAX = 2^31 - 1

If you look at the bits of INT_MAX, they are 0111...111, or one 0 + thirty-one 1's;

Then how about INT_MIN?

If this is the first time for you to think about this question, you may guess it may be thirty-two 1's. But actually it is not. It is 1000...000, or one 1 + thirty-one 0's. I know you may ask:

1. why?

2. if this is true, then what is the number with all bits of 1?

The first question is very good one, but I will not try to answer the question here, since it does involve some design logic back to old days of computer. There are good resources online about this. 

For the second question, the answer is -1. (What?) Such a fun world! isn't it?

The next topic is bit-wise operations. The common ones are: & (and), | (or), ^ (xor),  ~ (opposite or NOT), >> (left shift), and <<(rigth shift).

Besides the definitions, pay attention to the precedence of these operators. This will cause some hidden bugs in code if not handle correctly.

Finally we can go to the applications in coding! Yeahhh


Question List


Upper Layer


Comments

Post a Comment

Popular posts from this blog

Graph Question - Hard Level - Question 1

2246. Longest Path With Different Adjacent Characters You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them. Constraints: n == parent.length == s.length 1 <= n <= 10^5 0 <= parent[i] <= n - 1 for all i >= 1 parent[0] == -1 parent represents a valid tree. s consists of only lowercase English letters. Analysis For this question, we need to construct a graph, or more specifically, a n-nary tree. How to construct the graph/tree? What we only know is the parent array. So we need to go through the parent array and constr...
Post a Comment
Read more

Priority_queue - Question 4

973 K Closest Points to Origin Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2). You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in). Constraints: 1 <= k <= points.length <= 10^4 -10^4 < xi, yi < 10^4 Analysis: It is quite straightforward to find the K points that have the closest distances to the original point. Since we need to find the smallest values, the root of the priority_queue (pq) is the largest one for all the elements inside the pq. Once the size of pq is larger than K, we need to pop out one. See the code below: class Solution { public: typedef pair<int, int> pp; vector<vector<int>> kClosest(vector<vector<int>>& points, int k) { vector...
Post a Comment
Read more