First Look at Bit Manipulation
Recently, while doing leetcode problems I came across a problem in which the most optimal solution was the result of bit manipulation. I knew bits were the 0’s and 1’s in binary, but that was about it. I decided to dig a little deeper and share what I’ve found here.
What are Bits?
Bit is a portmanteau of binary digit. Binary meaning two. A single bit therefor has 2 states, most often true or false, this is generally represented as 1 or 0. Through a series of bits one may represent a piece of data such as a number. 8 bits is a byte, you may have heard the term 32 bit integer, this is an integer which is represented through 32 bits.
The easiest way to understand bits is with numbers. We are used to a decimal based number system, where we have the numbers 0 through 9, then to represent ten we roll over to the next slot starting with 1 again. With binary we only have 2 numbers to work with, 0 and 1.
So 0 is 0, and 1 is 1, but what happens when we want to represent 2? Well, we roll over to the next spot. Therefor 2 = 10 in binary. And then if we want to represent 3? Well 2 + 1 = 3, so in binary that would be 10 + 01, or 11. Then when we want to represent 4, we would need to move to the next spot again so 100. 5 is 101, 6 is 110, 7 is 111, 8 would roll over to 1000.
Are you seeing a pattern yet? Just as in a decimal system, each new place represents another power of 10, in binary each new place represents another power of 2. 2⁰ = 1 in this instance, but then 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ =16. Which correlates to how 10 = 2, 100 = 4, 1000 = 8, and 10000 = 16, in binary.
What is Bit Manipulation?
Bit manipulation is the process of logically or arithmetically manipulating bits. This is a pretty lame definition but hopefully it will clear up when we talk about bitwise operators, or the operators you use to perform these arithmetic or logical operations on said bits.
What is Bit Manipulation Used For?
Since bits are the lowest level that your computer expresses data, being able to express data in a series of bits is very space efficient. So it’s no surprise that bit manipulation comes in handy for things that require precision and efficiency, such as: low-level systems, encryption, data compression, and image processing. It also comes up frequently in competitive programming.
Bitwise Operators
The bitwise operators are:
- AND represented by &
- OR represented by |
- XOR, exclusive OR, represented by ^
- NOT represented by ~
- Right shift represented by >>
- Left shift represented by <<
AND
The & operator is used on bit patterns of equal length. If both numbers in the corresponding positions are 1, the resulting number is also 1, otherwise it is 0.
6 & 7 = 6
110 & 111 = 110
OR
The | operator is also used on bit patterns of equal length. If either number in the corresponding position is 1, the resulting number is also 1.
6 | 7 = 7
110 |111 = 111
XOR
The ^ operator is used on bit patterns of equal length. If the numbers in the corresponding positions are opposite, the resulting number is 1.
6 ^ 7 = 1
110 ^ 111 = 001
NOT
The ~ operator turns a binary number into its complement. That is, the number where every corresponding number is the opposite.
~7 = 0
111 = 000
~6 = 1
110 = 001
~5 = 2
101 = 010
NOTE: If you try this through code, you will more than likely get a different result. This is because the numbers you are using are probably 32-bit signed integers. So the number 5 is represented as 00000000000000000000000000000101, where the first 0 represents its sign (positive). Therefor its opposite is 11111111111111111111111111111010 which is -6. I don’t necessarily want to make this first look over complicated by discussing the way we convert a number from positive to negative in binary.
Right Shift
The >> operator takes all of the bits and shifts them to the right by the given amount, discarding the leftmost numbers, adding 0s to the right.
5>>1 = 2
101 >> 1 = 010
5>>2 = 1
101>>2 = 001
6>>1 = 3
110>>1 = 011
6>>2 = 1
110>>2 = 001
You may notice that for each right shift, it is like dividing by 2 to the power of whatever we are shifting by, and rounding down.
5 / 2¹ = 2.5 rounded down to 2
5/ 2² = 1.25 rounded down to 1
6/2¹ = 3
6/2² = 1.5 rounded down to 1
Left Shift
The << operator is the same as >> but shifting the other direction (add 0s to the left side).
5<<1 =10
101<<1 = 1010
5<<2 = 20
101<<2 = 10100
6<<1 = 12
110<<1 = 1100
6<<2 = 24
110<<2 = 11000
Just as >> is like dividing by 2 to the power of a number, << is like multiplying by 2 to that power.
5 * 2¹ = 10
5 * 2² = 20
6 * 2¹ = 12
6 * 2² = 24
In Conclusion…
One thing to note is that all of the operations which require bit patterns of equal length can easily be achieved by adding 0s to the left side of the lower number. For example:
2 |4 = 6
10 |100 = 110
010 | 100 = 110
This was just a beginning look at bits, and bitwise operators. Next week I will dive more into bits, including how to convert positive numbers to negative, and some efficient algorithms using bit manipulation.
